区间dp学习笔记

例题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;}