2017-11-01

区间dp

区间dp模板题和一般性的思路

一个大的区间可以分解为小的区间。并且这两个问题本质是一样的。并且可以通过合并子问题的过程得到较大区间的结果。
若使用递推的方式解决问题，那么要先枚举区间的长度。

题目

矩阵乘法：求一系列的矩阵的乘法，按照一定的结合律，使得运算量最小。

题解

枚举最后一次乘法的位置，转移的复杂度为O(n).
合法的子区间的个数，故状态数是O(\(n^2\)),总的时间复杂度为O(\(n^3\))

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int dp[maxn][maxn];
memset(dp, 0x3f, sizeof(dp));//因为为了求最小值，初始值的时候设为无穷大。
for(int i=1; i<=n; i++) dp[i][i] = 0;
int dfs(int l, int r){
    if(dp[l][r]!=0x3f3f3f3f) return dp[l][r];
    for(int i=l ;i<r; i++){
        dp[l][r] = min(dp[l][r], dfs(l, i)+dfs(i+1, r)+a[l-1]*a[i]*a[r]);//左边矩阵的次数+右边的次数+左右合并的次数。
    }
    return f[l][r];
}
printf("%d\n", dfs(1, n));

题目

括号匹配。给一个括号的序列。选择一个字序列，使匹配的括号数最大。

题解

发现模式规律：

空串括号匹配(初始化的时候)
若s括号匹配，那么(s)与[s]是括号匹配的
若s, t括号匹配，那么st是括号匹配的

对于区间[l, r]，若\(S_l == S_r\), 则其可由[l+1, r-1]转移得到。
枚举中间点m，认为是[l, m]和[m+1, r]的组合

代码

#include <bits/stdc++.h>
using namespace std;
bool match(int l, int r){
    char x = s[l];
    char y = s[r];
    return x == '('&&y == ')' || x == '['&&y == ']';
}
for(int i=1; i<n; i++)//初始化
    dp[i][i+1] = match(i, i+1);
for(int len = 2; len<n; len++){//枚举区间的长度
    for(int i=1, j; (j = i+len)<=n; i++ ){//第一种匹配的方式
        dp[i][j] = dp[i+1][j-1]+match(i, j);
    }
    for(int m=i; m<j; m++){//第二种划分的方法
        dp[i][j] = max(dp[i][j], dp[i][m]+dp[m+1][j]);
    }
}
printf("%d\n", f[1][n]<<1);

石子合并问题

N个石子排成一排，每次合并的代价为两堆石子的数量之和，并且只能是相邻的两堆石子合并。（想想不相邻的石子合并是什么问题）

f[i][j] = min{f[i][k]+f[k+1][j]}+a[i]+\(\ldots \)+a[j]，在第k个位置分割
预处理前缀和

#include <bits/stdc++.h>
using namespace std;
partial_sum(a+1, a+n+1, s+1);
for(int len = 1; len<n; len++){//枚举r-l
    for(int i=1, j; (j=i+len)<=n; i++){
        dp[i][j] = INT_MAX;
        for(int k=i; k<j; k++){
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
        }
        dp[i][j] += s[j]-s[i-1];
    }
}
printf("%d\n", f[1][n]);

变形

若N个石子绕成一个环，求最小的合并的个数。
method①：枚举断开的位置.时间复杂度O(\(n^4\))

method②：在原链的基础上，后面再接一条链。最后扫描一遍所有长度为n的合并的次数的最小值。时间复杂度为O(\(n^3\));

决策单调性和四边形不等式优化

上面的石子合并问题，可以优化到O(\(n^2\)).

定义：

对于区间[l, r],存在一个决策点k，使得分为区间[l, k]和区间[k+1, r]后的代建最小，记w[l][r] = k
经过找规律，打表，可以发现w[l][r-1]\(\le \)w[l][r]\(\le\) w[l+1][r].
通过决策单调性，可以将时间复杂度降为O(\(n^2\))

代码

partial_sum(a+1, a+n+1, s+1);
for(int i=1; i<n; i++){//初始化
    dp[i][i+1] = a[i] + a[i+1];
    w[i][i+1] = i;
}
for(int len = 2; len<n; len++){//枚举r-l
    for(int i=1, j; (j=i+len)<=n; i++){
        dp[i][j] = INT_MAX;
        for(int k = w[i][j-1]; k<=w[i+1][j]; k++){
            if(dp[i][j]<=dp[i][k]+dp[k+1][j]) continue;
            dp[i][j] = dp[i][k] + dp[k+1][j];
            w[i][j] = k;//记录决策点
        }
    }
    f[i][j] += s[j]-s[i-1];
}
printf("%d\n", f[1][n]);

未解决的问题

本文标题:区间dp

文章作者:Babydragon

发布时间:2017-11-01, 23:51:10

最后更新:2018-03-23, 13:35:12

原始链接:http://baolintian.github.io/2017/11/01/区间dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。