1. 全栈程序员必看首页

区间dp入门_状压dp

全栈程序员-用户IM • • 未分类

区间dp入门_状压dp一.什么是区间dp?顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。二.核心思路既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的…

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一.什么是区间dp?

        顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

二.核心思路

        既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。板子如下：

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

三.朴素区间dp（n^3)

1.例题：石子归并1

（1）传送门：戳我呀

（2）转移方程：

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

j~ends堆合并 = 较小的（原来， 分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量）

注：可以用sum[j] – sum[i – 1]表示i~j堆的重量！

（3）代码：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int stone[105];
int dp[105][105];
int sum[105];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dp,INF,sizeof(dp));
    for(int  i =1;i<=n;i++){
        scanf("%d",&stone[i]);
        sum[i] = sum[i - 1] + stone[i];//重量
        dp[i][i] = 0;
    }
    for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1]);//更新状态
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

四.题目变形（线性变环状）

1.例题：石子归并2

（1）题意：原题与上面相同，但是石子排列由线性排列变成环状排列，求解

（2）思路：环状以后合并区间的情况就可以从后往前合并，最后合并完成可能是1~n,2~n~1,3~n~2…..这种n个石子合并的情况。所以我们可以破环成链，将前n-1各元素也放到n后面构成一个线性的环状序列，在对这个序列dp即可

                                    区间dp入门_状压dp

（3）代码：codevs 2102 环状石子归并（求最大值和最小值）

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int stone[105];
int dpmin[205][205];//最小
int dpmax[205][205];//最大
int sum[205];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dpmin,INF,sizeof(dpmin));
    memset(dpmax,-1,sizeof(dpmax));
    for(int  i =1;i<=n;i++){
        scanf("%d",&stone[i]);
        sum[i] = sum[i - 1] + stone[i];
        dpmin[i][i] = 0;
        dpmax[i][i] = 0;
    }
    for(int i = 1;i<=n;i++){
        sum[i+n] = sum[i+n-1]+stone[i];//展开的n后面的n-1~1重量
        dpmin[i+n][i+n] = 0;
        dpmax[i+n][i+n] = 0;
    }
    for(int len = 1;len<=n;len++){//长度还是最大n
        for(int j = 1;j+len<=2*n;j++){//起点枚举最大到2*n-1,ends<=2*n-1
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//注意！i<ends！！！因为i=ends时，dp[ends+1][ends]是不成立的！
                dpmin[j][ends] = min(dpmin[j][ends],dpmin[j][i]+dpmin[i+1][ends]+sum[ends]-sum[j-1]);
                dpmax[j][ends] = max(dpmax[j][ends],dpmax[j][i]+dpmax[i+1][ends]+sum[ends]-sum[j-1]);
            }
        }
    }
    int ansmin = 0xfffffff;
    int ansmax = -1;
    for(int i = 1;i<=n;i++){
        ansmin = min(ansmin,dpmin[i][i+n-1]);//找1~n,2~n~1,3~n~2....的合并n个堆的中最大和最小的值
        ansmax = max(ansmax,dpmax[i][i+n-1]);
    }
    cout<<ansmin<<endl;
    cout<<ansmax<<endl;
    return 0;
}

五.时间优化（四边形优化，n^2)

1.思路

        在查找最优分割点的时候，我们浪费了大量时间。那么我们可以把最优分割点保存下来，在查找的时候利用保存的最优分割点来优化查找过程。

2.四边形不等式优化：

（1）功能：用来寻找，s[i][j](i~j的最优分割点）与其他分割点的关系

（2）不等式内容：如果某东西满足a<b<=c<d且f[a][c]+f[b][d]<=f[a][d]+f[b][c],则说这个东西满足四边形不等式。简而言之：交叉小于包含！

（3）结论关系：s[i][j-1]<=s[i][j]<=s[i+1][j] 

（4）证明过程：

0.证明w满足四边形不等式，这里w是m的附属量，形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]}，此时大多要先证明w满足条件才能进一步证明m满足条件

1.证明m满足四边形不等式

2.证明s[i,j-1]≤s[i,j]≤s[i+1,j]

（5）证明请参考：点击打开链接

3.代码：(以石子归并v2为例）

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int dp[2005][2005];
int sum[2005];
int relation[2005][2005];
int num[2005];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dp,0x3f,sizeof(dp));
    for(int i = 1;i<=n;i++){
        scanf("%d",&num[i]);
        dp[i][i] = 0;
        relation[i][i] = i;
        sum[i] = sum[i-1] + num[i];
    }
    for(int i = 1;i<=n;i++){
        sum[i+n] = sum[i+n-1] +num[i];
        relation[i+n][i+n] = i+n;//分割点初始化
        dp[i+n][i+n] = 0;
    }
    for(int len = 1;len<=n;len++){
        for(int j = 1;j+len<=2*n;j++){
            int ends = j+len - 1;
            for(int k = relation[j][ends-1];k<=relation[j+1][ends];k++){//k的范围
                if(dp[j][ends]>dp[j][k]+dp[k+1][ends]+sum[ends]-sum[j-1])
                {
                    dp[j][ends]=dp[j][k]+dp[k+1][ends]+sum[ends]-sum[j-1];
                    relation[j][ends] = k;
                }
            }
        }
    }
    int ans = 0xfffffff;//一定要开0xfffffff不然错QAQ
    for(int i = 1;i<=n;i++){
        ans = min(ans,dp[i][i+n-1]);
    }
    printf("%d\n",ans);
    return 0;
}

六.四道入门题目（难点在于怎么找状态转移方程）

1.Poj2955 括号匹配（一）

(1)题意：给出一个的只有'(‘,’)’,'[‘,’]’四种括号组成的字符串，求 最多 有多少个括号满足题目里所描述的完全匹配。

(2)思路：这里的状态转移是以一个if为基础的，如果s[i]与s[j]匹配，那么明显的dp[i][j] = dp[i+1][j-1]+2;然后在这个基础上枚举分割点k.

(3)状态转移方程：dp[i][j]表示第i~j个字符间的最大匹配字符数。

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]);

（4）代码：

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[105][105];
int main()
{
    char s[105];
    while(scanf("%s",s+1)!=EOF)
    {
        memset(dp,0,sizeof(dp));//dp初始化为0，因为一方面是找最大之，一方面初始匹配数为0
        int len = strlen(s+1);//dp[i][i]不用处理，因为自己和自己不匹配就是0
        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++){//k<j
                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        cout<<dp[1][len]<<endl;
    }
    return 0;
}

2.Poj1651 抽卡片

（1）题意：给你n个数字，要求不能删除两端点的数字，然后删除其他数字的代价是该数字和左右相邻数字的乘积，问把数字（除端点）删完后的最小总代价。

（2）思路：因为最后都要删掉中间所有的数字，所以我们分隔一个个小区间删数字，合并区间求最小。那么我们的状态就是目前删掉的数字区间，但是我们分割的时候的意思是抽一个卡片出来，所以这个卡片不能在已经抽出的状态里面，所以dp[i][j]里面是不包含j卡片的！

（3）状态转移方程：dp[i][j]表示抽出第i~j-1张卡片时候的最小值

dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] +num[i-1]*num[k]*num[j]);

（4）代码：

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[105][105];
int num[105];
int main()
{
    int N;
    cin>>N;
    memset(dp,0x3f,sizeof(dp));//dp初始化为inf,因为找最小值
    for(int i = 1;i<=N;i++){
        cin>>num[i];
        dp[i][i] = 0;//dp[i][i]要初始化，作为由小到大累计的初始条件，自己取出自己就是为0
    }
    for(int len = 1;len<=N;len++){
        for(int i = 2;i+len<=N+1;i++){//起点从2开始，因为不包括两端点
            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]+num[i-1]*num[k]*num[j]);
            }
        }
    }
    cout<<dp[2][N]<<endl;//由dp[i][j]的定义，输出合并第2~N-1个卡片的结果
    return 0;
}

3.整数划分（四）

（1）题意：给出两个整数 n , m ,要求在 n 中加入m – 1 个乘号，将n分成m段，求出这m段的最大乘积

（2）思路：这里给的乘号是有限个，所以状态方程里必须包含使用乘号的个数，此外还要包含区间长度。所以怎么用二维dp实现包含m和n，我们可以用dp[i][j]表示在第1~i个字符里插入j个乘号的最大值。

（3）状态转移方程 dp[i][j]表示在第1~i个字符里插入j个乘号的最大值；用num[i][j]表示第i~j个字符表示的数字；

dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k+1][i])

（4）代码：

#include <iostream>
#include<cstdio>
#include<cstring>
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));//初始化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];//初始插入0个乘号时是自己，由小到大累计的基础
        }
        for(int j = 1;j<m;j++){//乘号个数由1~m-1个
            for(int i = 1;i<=len;i++){//结尾坐标（表示长度）
                for(int k = 1;k<i;k++){//分割点插入第j个乘号
                    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;
}

4.最多回文子串 hdu4632

(1)题意：给你一个字符串，求出其最多的可构成的回文字串（不要求连续），注：这里不同的回文字串只要求位置不同即可视为不同，如：aaaaa 的最多回文子串数目是 31.

（2）思路：用dp[i][j]表示状态，表示i~j里最多的回文字串数目，假设现在我们要求dp[i][j]：

a.首先：由前一个状态知：dp[i][j] = dp[i+1][j]并上dp[i][j-1] （因为区间尽可能大而且状态要在dp[i][j]之前，而且回文子串不要求 连续），由容斥原理得：dp[i+1][j] U dp[i][j-1] = dp[i+1][j]+dp[i][j-1] – dp[i+1][j] n dp[i][j-1]

                                                                   =  dp[i+1][j]+dp[i][j-1] – dp[i+1][j-1]

注意：这是一个固定的状态，每一个状态都由这个公式推出初始状态，是必须的，不是可选择地

b.其次：如果s[i] == s[j] ,那么两端单独就可以构成回文子序列，而且与dp[i+1][j],dp[i][j-1],dp[i+1][j-1]，中的回文序列又可以构成新的回文序列，所以此时dp[i][j] = dp[i+1][j] U dp[i][j-1] + dp[i+1][j-1] +1;而dp[i][j]已经更新为 dp[i+1][j] U dp[i][j-1]，所以dp[i][j] = dp[i][j] + dp[i+1][j-1] +1;

(3)状态转移方程： dp[i][j]表示i~j内最多的回文字串数目

dp[i][j] = dp[i+1][j]+dp[i][j-1] -dp[i+1][j-1] (容斥）

if(s[i] == s[j]) dp[i][j] = dp[i][j] +dp[i+1][j-1] +1; （思维）

注：这里因为容斥时有减法，所以要先加上模再取模，要不会出现负数！

（4）代码：

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
char s[1005];
int dp[1005][1005];
int main()
{
    int T;
    scanf("%d",&T);
    int t = 0;
    while(T--){
        t++;
        scanf("%s",s+1);
        memset(dp,0,sizeof(dp));
        int len = strlen(s+1);
        for(int i = 1;i<=len;i++)dp[i][i] = 1;//自己是长度为1的
        for(int l = 1;l<=len;l++){
            for(int i = 1;i+l<=len+1;i++){
                int j = i+l-1;//容斥原理 dp[i][j] = dp[i+1][j]并dp[i][j-1] (因为是自序列可以不连续）
                dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+10007)%10007;
                if(s[i] == s[j])dp[i][j]=(dp[i][j]+dp[i+1][j-1] + 1)%10007;//如果两端相等，dp[i][j] = 原来的 + 两端与中间每一个回文也可以构成回文（dp[i+1][j-1]) + 两端单独构成一个回文（1）！！！
            }
        }
        printf("Case %d: %d\n",t,dp[1][len]);

    }
    return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/194032.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • <span role="heading" aria-level="2">图像的拼接—-RANSAC算法

    图像的拼接—-RANSAC算法

    图像的拼接—-RANSAC算法一、全景拼接的原理1.RANSAC算法介绍RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月2日
  • Java与C++的优劣：谁更胜一筹？零基础实习学C++还是java呢？

    Java与C++的优劣：谁更胜一筹？零基础实习学C++还是java呢？

    Java与C++的优劣：谁更胜一筹？零基础实习学C++还是java呢？很多人都说会C++就能会快掌握Jave。C++是不好学，但是我告诉你java也不好学。C++难是难在语言本身，java难是难在各种框架和库。你单纯学个java语法，你什么玩意也做不了，java的东西都在java之外。上图仅供娱乐，不过今天我们主要探讨Java与C++间的优劣。基础介绍Java与C++都拥有相当长的历史，且语法相当类似，并被众多业界巨头所采用。事实上，Java本来就是从C++衍生出来的。不过尽管相似，二者之间仍然存在显著区别。很多人都说会C++就能会快掌…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月8日
  • <span>zookeeper集群安装配置</span>

    zookeeper集群安装配置

    zookeeper集群安装配置

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年11月15日
  • 解决idea的控制台输出Tomcat日志乱码问题「建议收藏」 idea

    解决idea的控制台输出Tomcat日志乱码问题「建议收藏」

    解决idea的控制台输出Tomcat日志乱码问题「建议收藏」解决idea的控制台输出Tomcat日志乱码问题乱码原因由于window下的idea默认编码集都默认是GBK，而Tomcat目前版本是UTF-8，所以会出现乱码。第一种解决方案：将Tomcat输出日志的编码改为GBK在Tomcat的config目录下有一个logging.properties文件，文件中可以在五个地方设置编码，分别对应红色圆圈内五个日志输出文档（默认只选中了两个），将UTF-8的地方全改成GBK1catalina.org.apache.juli.FileHandler.l

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月25日
  • 基于springboot自定义事务注解「建议收藏」

    基于springboot自定义事务注解「建议收藏」

    基于springboot自定义事务注解1.开启注解支持(springboot默认支持注解)2.自定义注解接口3.写事务类4.写切面类2.自定义注解接口importjava.lang.annotation.*;/***注解类*/@Target(ElementType.METHOD)//定义注解用在方法上@Retention(RetentionPolicy.RUNTIME)//运行时注解@Documentedpublic@int

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年4月13日
  • 图像处理-激光测距技术&工业相机基本原理概述「建议收藏」

    图像处理-激光测距技术&工业相机基本原理概述「建议收藏」

    图像处理-激光测距技术&工业相机基本原理概述「建议收藏」激光测距技术与一般光学测距技术相比,具有操作方便、系统简单及白天和夜晚都可以工作的优点.与雷达测距相比,激光测距具有良好的抗干扰性和很高的精度,而且激光具有良好的抵抗电磁波干扰的能力,尤其在探测距离较长时,激光测距的优越性更为明显.激光测距技术是指利用射向目标的激光脉冲或连续波激光束测量目标距离的距离测量技术.比较常用的激光测距方法有脉冲法、相位法、三角法和干涉法激光测距.本文主要探讨下激光三角法的基本原理和工业相机原理：1.1激光三角法的基本原理光电技术的快速发展，以及计算.

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号