12-动态规划/02-区间DP

区间 DP

区间 DP 的状态定义为一个区间 [math]\displaystyle{ [l, r] }[/math]，通过枚举区间内的分割点 [math]\displaystyle{ k }[/math] 来合并两个子区间。

通用模板

// 枚举区间长度 len
for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++)
    {
        int r = l + len - 1;
        for (int k = l; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost(l, k, r));
    }

石子合并

有 [math]\displaystyle{ n }[/math] 堆石子排成一排，每次合并相邻两堆，代价为两堆石子数之和，求最小总代价。

int a[MAXN], pre[MAXN], dp[MAXN][MAXN];

memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++)
{
    dp[i][i] = 0;
    pre[i] = pre[i - 1] + a[i];
}

for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++)
    {
        int r = l + len - 1;
        int cost = pre[r] - pre[l - 1];
        for (int k = l; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost);
    }

回文串问题

求最长回文子序列：

// dp[l][r] = s[l..r] 的最长回文子序列长度
for (int i = 1; i <= n; i++)
    dp[i][i] = 1;

for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++)
    {
        int r = l + len - 1;
        if (s[l] == s[r])
            dp[l][r] = dp[l + 1][r - 1] + 2;
        else
            dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
    }