POJ 1651

简单DP，矩阵链乘思路

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn= 105;
const int INF= 0x3f3f3f3f;

int cs[maxn];
int dp[maxn][maxn];

int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	memset(dp, 0x3f, sizeof(dp));
	for (int i= 0; i< n; ++i){
		scanf("%d", cs+i);
	}

	int ui= n-1;
	for (int i= 0; i< ui; ++i){
		dp[i][i+1]= 0;
	}

	for (int d= 2; d< n; ++d){
		ui= n-d;
		for (int i= 0; i< ui; ++i){
			int j= i+d;
			int &s= dp[i][j];
			for (int k= i+1; k< j; ++k){
				s= min(s, cs[k]*cs[i]*cs[j]+dp[i][k]+dp[k][j]);
			}
		}
	}
	cout<<dp[0][n-1];

	return 0;
}

原文：https://www.cnblogs.com/Idi0t-N3/p/14178158.html