区间dp

区间dp：顾名思义，就是从小的区间推向大的区间。
区间dp的一般模板：

for(int len = 1;len<=n;len++)
{
    for(int j = 1;j+len<=n+1;j++)
    {
         int r = j+len - 1;
         for(int l = j;l<r;l++)
         {
                dp[j][r] = min(dp[j][r],dp[j][l]+dp[l+1][r]+number);//这里的number需要具体问题及具体分析。
         }
    }
}
1
2
3
4
5
6
7
8
9
10
11

我们以合并石子为例：

合并石子

做法：我们在看到这道题时主要的点就是不知道合并石子的顺序，枚举所有的区间，然后暴力所有的合并情况（这一个区间内哪一个石子最后合并进去）。

我们需要枚举哪些石子堆先合并，所以我们要从小到大枚举出所有的长度，然后再依次枚举所有状态即可，下面是参考代码：

#include 
using namespace std;
#define ll long long int
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 7;

int a[N], sum[N];
int cal(int l, int r) {
    return sum[r] - sum[l - 1];
}
int dp[N][N];

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];//前缀
    }
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len <= n; l++) {
            int r = l + len;
            dp[l][r] = inf;
            for (int k = l; k <= r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cal(l, r));
            }
        }
    }
    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
28
29
30
31

当然，也有加强版的区间dp，如果区间dp成了环，那么代码应该就有所变化了，下面是环形石子合并代码：
戳我

#include 
using namespace std;
#define ll long long int
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 7;

int a[N], sum[N];
int cal(int l, int r) {
    return sum[r] - sum[l - 1];
}
int dp[N][N];
int f[N][N];
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n + 1; i <= n * 2; i++)
        a[i] = a[i - n];
    for (int i = 1; i <= n * 2; i++)
        sum[i] = sum[i - 1] + a[i];
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n * 2; l++) {
            int r = l + len - 1;
            dp[l][r] = inf;
            f[l][r] = -inf;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cal(l, r));
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + cal(l, r));
            }
        }
    }
    int minx = inf, maxx = 0;
    for (int i = 1; i <= n; i++) {
        minx = min(minx, dp[i][i + n - 1]);
        maxx = max(maxx, f[i][i + n - 1]);
    }
    cout << minx << endl
         << maxx << 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
36
37
38
39
40
41

相对于的普通的变化就是环形的情况下任意一堆都可以是第一堆，这个题也用了环形问题的通解，就是将数组扩大两倍。

我们现在再做几道例题：
例题1：括号匹配
题意：找到最大的括号匹配数
做法：区间dp，和那个石子合并类似，dp[i][j]就是表示[i,j]内能够匹配的最大数量，所以如果s[i]和s[j]要是能匹配的情况下，先将dp[i][j]=dp[i+1][j-1]+2，完成初始的赋值（表示第一个括号和最后一个匹配），然后依次枚举区间即可。
下面是AC代码：

#include 
#include
#include
#include
using namespace std;
int dp[105][105];
int main()
{
    char s[105];
    while(scanf("%s",s+1)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int len = strlen(s+1);
        if(s[1]=='e')break;
        for(int l = 1;l<=len;l++){
            for(int i = 1;i+l<=len+1;i++){
                int j= i+l-1;
                if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){//如果匹配，先更新，不然的话无法实现最左边括号匹配的状态
                    dp[i][j] = dp[i+1][j-1]+2;
                }
                for(int k = i;k<j;k++)
                {
                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        cout<<dp[1][len]<<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

例题2：整数划分（四）
这个和那个合并石子有些不同的，我们可以将所有的操作看作是在区间[1,len]之内进行，所以我们可以将dp[i][j]表示为在[1,i]上进行操作然后放了j和括号的最大值，这样我们需要枚举三层，第一层是乘号的数量，第二层是区间，第三层是将最后一个乘号放在那个数的后面。
下面是参考的AC代码：

#include 
#include
#include
using namespace std;
typedef long long ll;
ll dp[50][50];
ll num[50][50];
int main()
{
    int T;
    scanf("%d",&T);
    char s[100];
    while(T--)
    {
        int m;
        scanf("%s%d",s+1,&m);
        int len = strlen(s+1);
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        for(int i = 1; i<=len; i++)
        {
            for(int j = i; j<=len; j++)
            {
                for(int k = i;k<=j;k++){
                    num[i][j]*=10;
                    num[i][j]+=(s[k]-'0');
                }
            }
            dp[i][0] = num[1][i];
        }
        for(int j = 1;j<m;j++){//枚举乘号的个数，这个尽量在最外层枚举，比较好写，也符合我们对于第三维的定义，枚举第j个放在哪，也可以样理解，我第三位枚举的是位置，所有一定是在某个位置后面，我只能放一个，所以这个不能放在第三维，但是可以放在第二维。
            for(int i = 1;i<=len;i++){//枚举长度
                for(int k = 1;k<i;k++){//在哪个整数后面放上乘号，注意不能放到最一个数的后面
                    dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k+1][i]);
                }
            }
        }
        cout<<dp[len][m-1]<<endl;//输出在1~len插入m-1个乘号的结果
    }
    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
36
37
38
39
40
41

下面是几道较难的区间dp
Link with Bracket Sequence II
题解：就是找到所有的括号匹配的种类。下面是AC代码：

#include
#include
#include
#include
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m;
int a[550];
int dp[550][550];
int dfs(int l,int r)
{
    if((r-l+1)%2) return 0;//奇数个括号
    if(r-l+1==0) return 1;
    if(r-l+1==2)
    {
        if(a[l]>0&&a[r]==-a[l]) return 1;
        else if(a[l]==0&&a[r]<0) return 1; 
        else if(a[l]>0&&a[r]==0) return 1;
        else if(a[l]==0&&a[r]==0) return m;
        else return 0;
    }
    if(dp[l][r]!=-1) return dp[l][r];//记忆化搜索
    int res=0;
    if(a[l]>0)
    {
        for(int i=l+1;i<=r;i+=2)
        {
            if(a[i]==-a[l]||a[i]==0) res=(res%mod+(dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod);
        }
    }
    else if(a[l]==0)
    {
        for(int i=l+1;i<=r;i+=2)//枚举区间长度的过程，必须都是偶数，这里也类似于剪了一个小枝条
        {
            if(a[i]<0) res=(res%mod+(dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod)%mod;
            if(a[i]==0) res=(res%mod+(m%mod*dfs(l+1,i-1)%mod*dfs(i+1,r)%mod)%mod)%mod;
        }
    }
    return dp[l][r]=res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                dp[i][j]=-1;
            }
        }
        for(int i=1;i<=n;i++) cin>>a[i];
        cout<<dfs(1,n)%mod<<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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

详细题解请戳我

还有就几道题现在找不到了，而且区dp还有四边形优化，持续更新中~~~~~~