区间dp问题
参考：
区间DP题型总结
区间DP概念
区间DP是线性DP的扩展，分阶段地划分问题，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
状态转移方程：
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]
或者
dp[i][j]=max{dp[i][k]+dp[k+1][j]}+cost[i][j]
区间DP的特点：
（1）合并：即将两个或多个部分进行整合，当然也可以反过来。
（2）特征：能将问题分解为能两两合并的形式。
（3）求解：将整个问题取最优值，枚举合并点，将问题分解为左右两个部分，最后合并的两个部分的最优值得到原问题的最优值。
简而言之：通过合并小区间的最优解进而得出整个大区间上的最优解。
思路+模板
将区间分割成一个个小区间，求解每个小区间上的最优解。
代码实现，可以枚举分割长度，起点和分割点，更新小区间的最优解。
1.枚举区间长度
2.枚举起点也得到了重点
3.枚举分割点即可
for(int len = 1; len <= n; len++) // 枚举长度
{
for(int i = 1; i + len <= n + 1; i++) // 枚举起点
{
int j = i + len - 1;
for(int k = i; k < j; k++) // 枚举分割点 注意没有等于号
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
xp[i][j] = max(xp[i][j], xp[i][k] + xp[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
例题
1.石子合并直线版
Description
一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100)，表示有n堆石子，。
二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）
Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11
思路：区间DP问题
定义dp[i][j]为将第i堆到第j堆石子合并获得的最小得分
状态转移
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
/*
数组a保存输入的数据
数组dp保存求最小得分时的动态规划状态转移数据
数组sum用于保存前缀和
数组xp保存求最大得分时的动态规划状态转移数据
*/
int n,a[maxn],dp[maxn][maxn],sum[maxn],xp[maxn][maxn];
int main(){
while(cin>>n){
memset(xp,0,sizeof(xp));
memset(sum,0,sizeof(sum));
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][i]=0;
xp[i][i]=0;
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
//枚举长度
for(int len=1;len<=n;len++){
//枚举起点,len是左闭右闭区间的长度
for(int i=1;i+len-1<=n;i++){
//j为终点
int j=i+len-1;
//枚举分割点
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
xp[i][j]=max(xp[i][j],xp[i][k]+xp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<dp[1][n]<<" "<<xp[1][n];
}
return 0;
}
2.石子合并圆形版
相比较于直线版的石子合并我们可以在后面加上一个相同大小的区间。可以模拟到圆环的状态。
Description
在圆形操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100)，表示有n堆石子，。
二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）
Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11
//相比较于直线版的石子合并我们可以在后面加上一个相同大小的区间。可以模拟到圆环的状态。
using namespace std;
const int maxn = 210;
/*
数组a保存输入的数据
数组dp保存求最小得分时的动态规划状态转移数据
数组sum用于保存前缀和
数组xp保存求最大得分时的动态规划状态转移数据
*/
int n, dp[maxn][maxn], xp[maxn][maxn], sum[maxn], a[maxn];
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(dp, 0x3f, sizeof(dp));
memset(xp, 0, sizeof(xp));
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
dp[i][i] = 0;
}
for(int i = 1; i <= n; i++)
{
sum[i + n] = sum[i + n - 1] + a[i];
dp[i + n][i + n] = 0;
}
//枚举长度
for(int len = 1; len <= n;len++)
{
//枚举起点
for(int i = 1; i + len -1 <= 2 * n; i++)
{
//终点
int j = len + i - 1;
//枚举分割点
for(int k = i; k < j; k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
xp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int maxns=-1,minns=0x3f3f3f3f;
for(int i=n;i<=2*n;i++){
maxns=max(xp[i-n+1][i],maxns);
minns=min(dp[i-n+1][i],minns);
}
cout<<minns<<" "<<maxns<<endl;
}
return 0;
}
NOI1995 石子合并
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分。
第一眼看到这个题目，肯定很多人会想“每次合并代价最小的两堆 难道不对吗？”
8 4 6 3 5
按照贪心 是62 但最优解是60…
好的，那我们还是开始想dp吧。
区间dp常用的一个状态就是dp[i][j]表示i~j这个区间的最优值是多少？
我们可以看出题目中这个合并过程，很像是区间dp的一种合并，也就是说dp[i][j]可以由dp[i][k]和dp[k+1][j]转移过来
那么我们自然而然的想到要枚举上一次合并是在哪个位置，也就是断点k，然后进行转移
很容易想到这样一个dp转移
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]
震惊！这不就是之前所讲的模型嘛？原来之前O（n^3）方的合并石子问题还可以优化
首先明确一点，cost[i][j]表示把第i堆到第j堆的石子和到一起的最后一步的代价，显然，之前无论怎么合并，最后一步的代价都是一样的，所以我们可以先预处理出这个cost数组，他等于cnt[j]-cnt[i-1]，其中cnt数组是前缀和
for一遍i，for一遍j，每算一次dp[i][j]还要for一遍k，自然是O(n^3)方，现在我们来按照规则判断是否可以用四边形优化
Brackets POJ - 2955(括号匹配)
1.题意：只有两种括号( )和[ ], 要求最大的括号匹配数。
2.如果s[i] 与s[j]匹配， 则dp[i][j] = dp[i + 1][j-1] + 2;
并且我们需要找的是最大的匹配数目，所以不断更新区间情况，来使达到最大最优匹配状态。
3.状态转移方程
if(s[i] 与 s[j]匹配） dp[i][j] = d[[i+1][j-1] +2;
dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 110;
bool match(char a, char b)
{
if(a == '(' && b == ')' || a == '[' && b == ']')
return 1;
return 0;
}
char ch[maxn];
int dp[maxn][maxn];
int main()
{
while(scanf("%s", ch + 1) != EOF)
{
if(ch[1] == 'e') break;
int n = strlen(ch + 1);
memset(dp, 0, sizeof(dp));
for(int len = 1; len <= n; len++)
{
for(int i = 1; i + len <= n + 1; i++)
{
int j = i + len - 1;
if(match(ch[i], ch[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]);
}
}
printf("%d\n", dp[1][n]);
}
return 0;
}
leetcode相关例题
背景：给定一个序列或字符串要进行一些操作，从最后一步出发，要将序列或字符串去头、去尾，如果做过最长回文子串，你就就可以想一下这样子的操作。区间型 dpdp 一般用 dp[i][j]dp[i][j] ，ii 代表左端点，jj 代表右端点，若有其他维度可再添加，若两个端点之间存在联系，则可再压缩空间。力扣上还有一些题也属于区间 dpdp，我推荐大家做一下，下面列出了一些
87. 扰乱字符串
参考：
简单易懂的dp思路，逐行解释
详细通俗的思路分析，多解法
递归思路
这道题很容易想到用递归的思想去解，假如两个字符串 great 和 rgeat。考虑其中的一种切割方式。
第 1 种情况：S1 切割为两部分，然后进行若干步切割交换，最后判断两个子树分别是否能变成 S2 的两部分。
第 2 种情况：S1 切割并且交换为两部分，然后进行若干步切割交换，最后判断两个子树是否能变成 S2 的两部分。
//带有备忘录的递归解法
class Solution {
public:
unordered_map<string,bool> mp;
bool helper(string& s1,string& s2){
if(s1.size()!=s2.size()) {
mp[s1+s2]=false;
return false;
}
if(s1==s2){
mp[s1+s2]=true;
return true;
}
//判断字符个数不一致，直接返回false
//做了这个判断，效率提高不少
int c[26] = {0};
for(int i=0;i<s1.length();i++)
{
c[s1[i]-'a']++;
c[s2[i]-'a']--;
}
for(int i=0;i<26;i++)
if(c[i] != 0){
mp[s1+s2]=false;
return false;
}
if(mp.count(s1+s2)){
return mp[s1+s2];
}else{
//递归思路
//枚举切割点k
for(int k=1;k<s1.size();k++){
//只要有一个切割点满足了，就返回true;
//情况1：s1的第一步只是切割，然后递归处理左右子串与s2的关系
if(isScramble(s1.substr(0,k),s2.substr(0,k))
&&isScramble(s1.substr(k,s1.size()-k),s2.substr(k,s2.size()-k))){
mp[s1+s2]=true;
return true;
}
//情况2：s1的第一步切割后，并且交换，然后递归处理左右子串与s2的关系
if(isScramble(s1.substr(k,s1.size()-k),s2.substr(0,s2.size()-k))
&&isScramble(s1.substr(0,k),s2.substr(s2.size()-k,k))){
mp[s1+s2]=true;
return true;
}
}
mp[s1+s2]=false;
return false;
}
}
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
if(s1==s2) return true;
return helper(s1,s2);
}
};
动态规划思路
初步分析
给定两个字符串 T 和 S，假设 T 是由 S 变换而来
如果 T 和 S 长度不一样，必定不能变来
如果长度一样，顶层字符串 S 能够划分为S 1 S_1S1和S 2 S_2S2，同样字符串 TT 也能够划分为 T_1和 T 2 T_2T2
情况一：没交换，S 1 = = > T 1 S_1 ==> T_1S1==>T1，S 2 = = > T 2 S_2 ==> T_2S2==>T2
情况二：交换了，S 1 = = > T 2 S_1 ==> T_2S1==>T2，S 2 = = > T 1 S_2 ==> T_1S2==>T1
子问题就是分别讨论两种情况，T 1 T_1T1是否由 S 1 S_1S1 变来，T 2 T_2T2是否由 S 2 S_2S2变来，或 T 1 T_1T1是否由 S 2 S_2S2变来，T 2 T_2T2是否由S 1 S_1S1变来。
状态定义
dp[i][j][k][h] 表示 T[k…h]是否由 S[i…j]变来。
由于变换必须长度是一样的，因此这边有个关系 j - i = h - k，可以把四维数组降成三维。
dp[i][j][len]表示从字符串 S中 i开始长度为 len的字符串是否能变换为从字符串 T中 j开始长度为len的字符串
转移方程
base case
最后的结果
dp[0][0][N]
代码如下
class Solution {
public:
//区间dp
//dp[i][j][k][h]表示s1[i]~s1[j]与s2[k]~s2[h]是否是满足，因为j-i==h-k，所以可以减少一个状态
//dp[i][j][len]表示已s[i]开头，长度len的字符串与已s2[j]开头，长度len的字符串是否满足
//状态转移
/*枚举len的分割点，对于每一个长度len,只要有一个分割点满足，dp[i][j][len]就为true
for(int len=2;len<s1.size();len++)
for(int k=1;k<len;k++ )
//第一种情况 仅分割
if(dp[i][j][k]&&dp[i+k][j+k][len-k])
dp[i][j][len]=true;
//第二种情况，分割后交换
if(dp[i][j+len-k][k]&&dp[i+k][j][len-k]){
dp[i][j][len]=true;
*/
//base case
//dp[i][j][0]=true;
//dp[i][j][1]=(s1[i]==s2[j])
//返回结果为
//dp[0][0][s1.size()]
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
if(s1==s2) return true;
//当s1.size()!=s2.size(),这里还可以做一个检查,效率高了不少
//如果s1,s2中每一个字符出现的次数不一样，直接放回false
int c[26]={0};
for(int i=0;i<s1.size();i++){
c[s1[i]-'a']++;
c[s2[i]-'a']--;
}
for(int i=0;i<26;i++){
if(c[i]!=0) return false;
}
int N=s1.size();
vector<vector<vector<bool>>> dp(N,vector<vector<bool>>(N,vector<bool>(N+1)));
//base case
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dp[i][j][0]=true;
dp[i][j][1]=(s1[i]==s2[j]);
}
}
//状态转移
for(int len=2;len<=N;len++){
for(int i=0;i<=N-len;i++){
for(int j=0;j<=N-len;j++){
//k表示分割给左边的区间长度
//只要有一个分割满足，dp[i][j][len]=true;
for(int k=1;k<len;k++){
//第一种情况 仅分割
if(dp[i][j][k]&&dp[i+k][j+k][len-k]){
dp[i][j][len]=true;
break;
}
//第二种情况，分割后交换
if(dp[i][j+len-k][k]&&dp[i+k][j][len-k]){
dp[i][j][len]=true;
break;
}
}
}
}
}
return dp[0][0][N];
}
};
5. 最长回文子串（状态定义，转移，遍历方向，base case,返回结果）
状态定义
dp[i][j] 表示子串 s[i…j] 是否为回文子串，这里子串 s[i…j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]
状态转移
注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
base case
当i>j;时 不用考虑；
当i==j;时 dp[i][j]=true;
最后结果
枚举i和j，找出dp[i][j]==true中 j-i+1的最大值
代码示例
class Solution {
public:
string longestPalindrome(string s) {
int N=s.size();
if(N<2) return s;
//dp[i][j]：s[i]~s[j]是否时回文串
vector<vector<int>> dp(N,vector<int>(N));
for(int i=0;i<N;i++){
dp[i][i]=true;
}
//注意这里i,j枚举时的范围和遍历方向（这里只能斜着向下，或者由底向上）
//关于最后返回的结果，也可以在循环中挑战全局最大的操作
int start=0,res=1;
for(int i=N-2;i>=0;i--){
for(int j=i+1;j<N;j++){
if(s[i]==s[j]){
//[i,j]中间没有字符了，可以直接判断
if(j-i==1)
dp[i][j]=true;
else
dp[i][j]=dp[i+1][j-1];
}else
dp[i][j]=false;
if(dp[i][j]&&j-i+1>res){
res=j-i+1;
start=i;
}
}
}
return s.substr(start,res);
}
};
516. 最长回文子序列
516. 最长回文子序列
状态定义
dp[i][j] 表示子串 s[i…j] 的最长回文子序列的长度
状态转移
注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要
if(s[i]==s[j]){
dp[i][j]=2+dp[i+1][j-1];
}else
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
base case
当i>j;时 dp[i][j]=0;
当i==j;时 dp[i][j]=1;
最后结果
dp[0][N-1]
代码示例
class Solution {
public:
int longestPalindromeSubseq(string s) {
int N=s.size();
if(N<2) return N;
//dp[i][j]表示s[i]~s[j]之间形成的子串符的最长回文子序列的长度
vector<vector<int>> dp(N,vector<int>(N));
//base case
for(int i=0;i<N;i++){
dp[i][i]=1;
}
//填表方向很重要，必须保证小问题的解先被求出来
//这里只能选择由底向上，或者斜着向下
for(int i=N-2;i>=0;i--){
for(int j=i+1;j<N;j++){
if(s[i]==s[j]){
dp[i][j]=2+dp[i+1][j-1];
}else
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][N-1];
}
};