题解：从i到j合并的最小值：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]); 最后dp[1][n]即为所求结果。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define CLR(a,b) memset((a),(b),sizeof((a))) 5 using namespace std; 6 7 const int inf = 0x3f3f3f3f; 8 const int N = 101; 9 int n; 10 int a[N]; 11 int dp[N][N];//i到j合并的最小值 12 int sum[N]; 13 int main(){ 14 int t, i, j, k, len; 15 sum[0] = 0; 16 scanf("%d", &n); 17 for(i = 1; i <= n; ++i){ 18 scanf("%d", &a[i]); 19 sum[i] = sum[i - 1] + a[i]; 20 } 21 for(i = 1 ;i <= n; ++i) 22 dp[i][i] = 0; 23 for(len = 2; len <= n; ++len){//合并的长度 24 for(i = 1; i <= n - len + 1; ++i){//起点 25 j = i + len - 1;//终点 26 dp[i][j] = inf; 27 for(k = i; k < j; ++k){ 28 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]); 29 } 30 } 31 } 32 printf("%d ", dp[1][n]); 33 return 0; 34 }