区间dp
(区间dp) $O(n^3)$
一类有意思的题目,新的dp思路
时间复杂度
n^3
C++ 代码
#include <iostream>
using namespace std;
const int N = 310;
int s[N], f[N], dp[N][N]; // 前缀和数组和dp数组
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> f[i-1];
s[i] = s[i-1] + f[i-1];
}
// 区间dp 先遍历长度
for(int len = 2; len <= n; len ++)
// 遍历完长度之后遍历每个点在这个长度下的效果
for(int i = 0; i + len - 1 < n; i ++)
{
int r = i + len - 1;
dp[i][r] = 1e8; // 设为最大
for(int j = i; j < r; j ++)
dp[i][r] = min(dp[i][r], dp[i][j] + dp[j + 1][r] + s[r + 1] - s[i]);
}
cout << dp[0][n-1];
return 0;
}