dp区间问题~~~~

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

int n,a[1001],dp[1001][1001],sum[1001];

int main()

{

cin >> n;

for (int i = 1; i <= n; i++)

{

cin >> a[i];

sum[i] = sum[i - 1] + a[i];

}

for (int len = 1; len < n; len++)

{

for (int i = 1; i + len <= n; i++)

{

int j = i + len;

for (int k = i; k < j; k++)

{

if(dp[i][j])

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]+ sum[j] - sum[i - 1])  ;

else 

dp[i][j]= dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];

}

}

}

cout << dp[1][n] << endl;

return 0;

}