一, 区间 DP
顾名思义区间 DP 就是在区间上进行动态规划, 先求出一段区间上的最优解, 在合并成整个大区间的最优解, 方法主要有记忆化搜素和递归的形式.
顺便提一下动态规划的成立条件是满足最优子结构和无后效性!
二, 经典例题分析:
1. 石子合并:
一条直线上有 N 堆石子, 现在要将所有石子合并成一堆, 每次只能合并相邻的两堆, 合并花费为新合成的一堆石子的数量, 求最小花费.
分析:
一般看到最小, 最短这样的字眼, 可以往动态规划的方向思考, 显然当我任选两堆合并时, 只会影响下一次选择, 不会对再后来的选择有影响, 这时候我们几乎可以确认用 DP 了
1 堆: 花费为 0.
2 堆: 花费为 sum[2].
3 堆: 花费为 min(a[1]+a[2],a[2]+a[3])+sum[3].
如果我们有 N 堆, 最后一次合并一定是将两堆合并成一堆, 那两堆一定都是最少花费, 由此往下想: 那两堆肯定也是有最优的两堆合并, 这样就是一个递归过程.
所以我们可以想办法找出每个区间划分为两个最少花费区间的点, 这就是第一个模型:
第一个模型: 将大区间划分为两个小区间.
此题我们规定 dp[i][j]为合并第 i 堆到第 j 堆的最小花费.
DP 方程为: dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[j]-sum[i-1].
- memset(dp,Ox3f,sizeof(dp))
- for(int i=1;i<=dp.size();i++){
- dp[i][i]=0;// 将一堆石子合并花费为 0
- sum[i][i]=stones[i];// 合并第 i 堆到第 j 堆的花费.
- }
- for(int len=1;len<n;len++){
- // 区间长度
- for(int i=1;i<=n&&i+len<=n;i++{
- // 区间起点
- int j=i+len;// 区间终点
- for(int k=i;k<=j;k++){
- // 区间划分点
- sum[i][j]=sum[i][k]+sum[k][j];
- dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j];
- }
- }
- }
我们再看回 LeetCode 合并石子:
与例题不同的是此题是给定一个 K, 要将 K 长度内的石子合并(我们知道石子是一行排列), 换汤不换药, 仍然是区间 DP 解法, 只是将相邻两堆改成了相邻 K 堆:
本来我们只需将区间划分为任意两部分, 如今我们要将区间这样划分: 一部分长度为 K-1, 另一部分看作为一整堆, 这样最后才能合并为一整堆, 所以我们要做的改变只是将划分点每次移动的距离由 1 变为 K-1,
保证左边部分为 K-1 的整数倍.
由此我们得出要有结果, stones 长度必须满足: j-i%K-1==0.
- int len=stones.length;
- if((len-1)%(K-1)!=0)return -1;
- int[][] dp=new int[len][len];
- int[] sum=new int[len+1];
- for(int i=0;i<len;i++){
- dp[i][i]=stones[i];
- sum[i+1]=sum[i]+stones[i];
- }
- for(int j=1;j<len;j++){
- for(int i=j-1;i>=0;i--){// 只需考虑能最后能求解的子区间, 因为最后不会用到不能求解的
- dp[i][j]=dp[i][i]+dp[i+1][j];// 划分 i,i+1-j 两部分
- for(int k=i+K-1;k<j;k+=K-1){
- dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]);//DP 方程: 其中若 i-j 不是 K-1 的整数倍则继续 DP 时不会用到 DP[i][j].
- }
- if((j-i)%(K-1)==0){// 最后合并.
- dp[i][j]+=sum[j+1]-sum[i];
- }
- }
- }
- return dp[0][len-1]-sum[len];// 每次小区间合并时都已计算合并时的花费所以需要减去.
这就是对第一模型的例题分析, 都是将大区间划分为小区间, 求取最优解.
2. 括号匹配:
给定一个括号 ()[] 组成的字符串, 你要找到一个最长的合法的子序列, 对于一个字序列, 其中的括号一定有另一个相对应.
我们先尝试用上一模型解决试试:
规定 dp[i][j]为第 i 个字符到第 j 个字符之间的最长匹配序列.
长度为 N 时, 我们可以先检测 a[i]和 a[j]是否匹配, 如果匹配, dp[i][j]=dp[i+1][j-1]+2, 否则, 就可以按第一模型处理, 从任意位置划分为两个区间: dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j].
- for (int len = 2; len <= n; len++)
- {
- for(int i = 1, j = len; j <= n; i++, j++)
- {
- if((a[i]=='('&&a[j]==')') || (a[i]=='['&&a[j]==']'))//i,j 位置能匹配
- dp[i][j] = dp[i+1][j-1] + 2;
- for (int k = i; k <j; k++)// 任意位置划分为两个区间
- if(dp[i][j] < dp[i][k] + dp[k+1][j])
- dp[i][j] = dp[i][k] + dp[k+1][j];
- }
但这不是我们想要的第二个模型, 假设我们只考虑 [i,j] 是由 [i+1,j] 在前面加一个字符的情况, 如果 a[i+1]到 a[j]没有和 a[i]匹配的, 那么 dp[i][j]=dp[i+1][j], 如果匹配(i<k<=j), 那么 dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);
比如:[xxxxx]yyyyy 通过括号分成两个子串.
所以第二种模型就是根据匹配信息把区间划分为 [i+1,k-1] 和[k+1,j]:
- for (int len = 2; len <= n; len++)
- {
- for(int i = 1, j = len; j <= n; i++, j++)
- {
- dp[i][j] = dp[i+1][j];// 不能匹配
- for (int k = i; k <= j; k++)// 能匹配
- if((a[i]=='('&&a[k]==')') || (a[i]=='['&&a[k]==']'))
- dp[i][j] = max(dp[i][j], dp[i+1][k-1] + dp[k+1][j] + 2);
- }
- }
- Cheapest Palindrome:
n 个字符组成的长度为 m 的字符串, 给出增删字符的花费, 可在字符串的任意位置增删字符, 求把字符串修改为回文串的最小花费.
例: n=3,m=4 组成 abcd,
a:1000,1000,b:350,700,c:200 800
这题分四种情况: 假设有字符串: Xxxx...xxY
1. 去掉 X, 取 xx..xY 回文;
2. 去掉 Y, 取 Xx...x 回文;
3. 在左边加上 X,Xxx...xYX 回文;
4. 在右边加上 Y, 取 YXxx...x 回文;
规定 dp[i][j]为把 [i..j] 区间改为回文串的最小花费
我们得出 DP 方程: dp[i][j]=min(dp[i][j],dp[i+1][j]+min(add[a[i]-'a']+sub[a[i]-'a'])),// 增删 X 时
- dp[i][j]=min(dp[i][j],dp[i][j-1]+min(add[a[i]-'a']+sub[a[i]-'a'])),// 增删 Y 时
- for (int len = 2; len <= m; len++)
- for(int i = 1, j = len; j <= m; i++, j++)
- {
- dp[i][j] = min(dp[i][j], min(add[a[i]-'a'],sub[a[i]-'a']) + dp[i+1][j]);// 增删 X 时
- dp[i][j] = min(dp[i][j], dp[i][j-1] + min(add[a[j]-'a'],sub[a[j]-'a']));// 增删 Y 时
- if (a[i] == a[j])
- {
- if (len==2)
- dp[i][j] = 0;
- else
- dp[i][j] = min(dp[i][j], dp[i+1][j-1]);// 相等时就等于 [[i+1..j-1] 回文的长度.
- }
- }
这就是我们第三个模型只考虑左右边界, 不需要枚举区间 k->[i,j];
4. 总结:
区间 DP 最重要的时理解大区间和小区间之间的联系, 才能写出 DP 方程, 其实也可以将其看成是一个递归过程大区间由小区间得出, 小区间由小小区间得出.
来源: http://www.bubuko.com/infodetail-3462112.html