例题1：洛谷 P1775
我们可以设 dp[l][r] 为将区间 [l,r] 区间内的所有石子都合并成一堆时造成的最小代价。
如何求出 dp[l][r] 呢？此时我们可以枚举一个断点 k，把 [l,r] 区间分成两个区间：$[l,k]$ 和 [k+1,r]，很明显，k∈ [l,r-1]
现在就很容易推出状态转移方程了。也就是把 [l,k] 合成一堆石子花费的代价加上 [k+1][r] 合成一堆石子花费的代价加上 [l,r] 区间石子个数的总和（也就是把这两个区间各自合成一堆后再合成产生的代价）
此时我们可以使用一个前缀和数组 sum[i]，来表示区间石子的总和。
转移方程：dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1])
#include#include<string.h>using namespace std;int n;int a[310];int sum[310];int dp[310][310];int main (){ memset(dp, 0x3f, sizeof(dp)); cin >> n; for(int i = 1; i <= n; i ++){ cin >> a[i]; sum[i] = sum[i - 1] + a[i]; dp[i][i] = 0;//只有一堆不需要代价 } for(int len = 2; len <= n; len ++){ for(int l = 1; l + len - 1 <= n; l ++){ int r = l + len - 1; for(int k = 1; k <= r - 1; k ++){//断点 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + (sum[r] - sum[l - 1])); } } } cout << dp[1][n]; return 0;}