当前位置:   article > 正文

区间dp入门——总结+习题+解析_区间dp 题解

区间dp 题解

前天学长拉了个区间dp的专题,花了两个做,今天就来做个总结吧!!!

区间dp其实就是一种建立在线性结构上的对区间的动态规划,dp本来就是很奇妙的东西,也没有什么套路,就是一种思考的数学思维方式,只有做足够多的题并且想的足够多才可能在比赛中做出来。

区间dp,顾名思义,在区间上dp,大多数题目的状态都是由区间(类似于dp[l][r]这种形式)构成的,就是我们可以把大区间转化成小区间来处理,然后对小区间处理后再回溯的求出大区间的值,主要的方法有两种,记忆化搜索和递推。

在用递推来求解时,关键在于递推是for循环里面的顺序,以及dp的关键:状态转移方程。

当然大部分的区间dp都是有特点的,我们可以考虑符合什么条件下,大区间可以转化成小区间,然后找出边界条件,进行dp求解。

区间dp也有很经典的板子部分,下面抛出代码和解析:

  1. memset(dp,0,sizeof(dp))//初始dp数组
  2. for(int len=2;len<=n;len++){//枚举区间长度
  3. for(int i=1;i<n;++i){//枚举区间的起点
  4. int j=i+len-1;//根据起点和长度得出终点
  5. if(j>n) break;//符合条件的终点
  6. for(int k=i;k<=j;++k)//枚举最优分割点
  7. dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程
  8. }
  9. }

当然dp数组的维度和边界条件以及转移方程都是可变的,但是很多简单题都是这样可以做出来的,难题也都是情况更复杂了些,其最基本的思想还是不变的。

区间dp大部分的题目还有一种优化,因为我们很容易知道正常的区间dp时间复杂度为O(n^3)的,对于有的n是1000的,会超时

这时候就要用到一个经典的优化可以把它优化到:O(n^2),其实证明很难理解,但是大部分题都不会卡,因为dp已经很难了。

就算需要四边形优化,也就是多开一个数组s的事,在枚举最优分割点时,再缩小一下枚举范围,经典的用空间换时间的做法。

下面抛出基于四边形优化的代码。

  1. for(int len=2;len<=n;len++){
  2. for(int i = 1;i<=n;i++){
  3. int j = i+len-1;
  4. if(j>n) break;
  5. for(int k = s[i][j-1];k<=s[i+1][j];k++){
  6. if(dp[i][j]>dp[i][k]+dp[k+1][j]+w[i][j]){
  7. dp[i][j]=dp[i][k]+dp[k+1][j]+w[i][j];
  8. s[i][j]=k;
  9. }
  10. }
  11. }
  12. }

具体的证明过程可以参考这篇博文:戳我戳我

区间dp的知识点其实不多,最重要的还是在状态转移方程这一块,当然这里也有一些经典而且有意思的题目给大家。


先给出一些经典区间dp题型:石子合并环型石子匹配括号匹配问题括号匹配变形整数划分,最优三角形剖分,最优矩阵链乘。(最后两个题型在最后给出链接,kuangbin带你飞专题里面有)

然后就可以做一下比较有意思的题目,比如kuangbin带你飞区间dp专题,当然还有其他经典题型,以后再补。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/498812
推荐阅读
相关标签
  

闽ICP备14008679号