概述

区间DP：指在一段区间上进行的一系列动态规划
对于区间DP这一类问题，我们需要计算区间$[1,n]$的答案，通常用一个二维数组$dp$表示，其中$dp[x][y]$表示区间$[x,y]$
有些题目，$dp[l][r]$由$dp[l][r-1]$与$dp[l+1][r]$退到；也有题目，我们需要枚举$[l,r]$内的中间点，由两个子问题合并得到，也就是说$dp[l][r]$由$dp[;][l]$与$dp[k+1][r]$推得，其中$l\le k<r$
对于长度为n的区间DP，我们可以先计算$[1,1],[2,2]...[n,n]$的答案，再计算$[1,2],[2,3],...[n-1,n]$，以此类推，直到得到原问题的答案

例题：合并石子

题目

当前有 $N$ 堆石子，他们并列在一排上，每堆石子都有一定的数量。我们需要把这些石子合并成为一堆，每次合并都只能把 相邻 的两堆合并到一起，每一次合并的代价都是这两堆石子的数量之和，经过 $N-1$ 次合并后成为一堆。求把这些石子合并成一堆所需的最小代价。

解析

根据动态规划的思想，我们只需要求出没两堆石子合并的最小代价，然后再求出每三堆石子合并的最小代价，并以此类推就能求出$n$堆石子合并的最小代价。
我们把$dp[i][j]$定义为合并第$i$堆石子到第$j$堆石子所需的最小代价
$a[i]$为合并第$i$个石子的代价
很容易得到$dp[i][j]=min(dp[i][k]+dp[k+1][j])+{\sum }_{k=i}^{j}a\left[k\right]$，我们可以用前缀和计算${\sum }_{k=i}^{j}a\left[k\right]$，也就是定义$sum[i]={\sum }_{k=1}^{i}a\left[k\right]$，那么${\sum }_{k=i}^{j}a\left[k\right]=sum[j]-sum[i-1]$,所以$dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[j]-sum[i-1]$
显然，通过这个式子，我们可以按区间的长度从小到大的顺序来枚举不断让石子合并，最后就能获得合并一堆石子的代价
时间复杂度就是$O(n^3)$

示例代码

#include <iostream>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int stone[105], sum[105], dp[105][105], n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stone[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + stone[i];
        dp[i][i] = 0;
    }
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            dp[i][j]+=sum[j]-sum[i-1];
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

例题：涂色

题目

假设你有一条长度为 5 的木版，初始时没有涂过任何颜色。你希望把它的 5 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 55 的字符串表示这个目标$RGBGR$。

每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成 $RRRRR$ ，第二次涂成 $RGGGR$ ，第三次涂成 $RGBGR$ ，达到目标。

用尽量少的涂色次数达到目标。`

解析

我们把 问题看作一个长度为n的字符串s，字符串每种字母代表一种颜色
用$dp[x][y]$表示让区间$[x,y]$满足条件的最小次数。然后我们按照区间长度从小到大枚举每个区间

如果$s[x]==s[y]$
我们可以先把$[x,y]$整体涂成一个颜色，然后再去处理$[x+1,y-1]$。对应的动态转移方程就是
$$dp[x][y]=min(dp[x],dp[x+1][y-1]+1)$$
或者对应区间$[x,y-1]$，因为x是最边上的位置，所以最有情况下，一定可以第一个涂x位置，这样我们可以让这次涂色延长到y，这样实际上y也就顺带满足条件了，区间$[x+1,y]同理
所以动态转移方程为
$$dp[x][y]=min(dp[x][y-1],dp[x+1][y])$$

如果$s[x]!=s[y]$，那么实际上x和y没有关系，所以我们可以把区间分成两部分来完成，一部分包含x，一部分包含y
所以动态转移方程为
$$\forall x\le k<y,dp[x][y]=min(dp[x][y],dp[x][k]+dp[k+1][y])$$

代码实现

首先，先将整个dp数组都初始化为无穷大，方便后面min的操作。
然后把$dp[i][i]$都设为1，因为单独一个格子只能通过一次涂色涂好
接着，开始编写动态规划递归部分，首先从小到大枚举区间长度l，然后枚举i的起点i，最大枚举到s.size()-l+1，终点为i+l-1
根据解析中的动态转移方程写即可，最后输出dp[0][s.size()-1]

示例代码

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[55][55];
int main() {
    string s;
    cin >> s;
    memset(dp, 0x3f, sizeof(dp));
    for(int i=0;i<s.size();i++){
        dp[i][i]=1;
    }
    for(int l=2;l<=s.size();l++){
        for(int i=0;i<s.size()-l+1;i++){
            int j=i+l-1;
            if(s[i]==s[j]){
                if(l==2){
                    dp[i][j]=1;
                }
                else{
                    dp[i][j]=min(min(dp[i+1][j],dp[i][j-1]),dp[i+1][j-1]+1);
                }
            }
            else{
                for(int k=i;k<j;k++){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
    }
    cout<<dp[0][s.size()-1]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35