查看“︁12-动态规划/02-区间DP”︁的源代码


== 区间 DP ==

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

=== 通用模板 ===

<syntaxhighlight lang="cpp">
// 枚举区间长度 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));
    }
</syntaxhighlight>

== 石子合并 ==

有 <math>n</math> 堆石子排成一排，每次合并相邻两堆，代价为两堆石子数之和，求最小总代价。

<syntaxhighlight lang="cpp">
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);
    }
</syntaxhighlight>

== 回文串问题 ==

求最长回文子序列：

<syntaxhighlight lang="cpp">
// 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]);
    }
</syntaxhighlight>

[[Category:动态规划]]
[[Category:三三文档]]