一,动态规划
1.数字三角形模型:
AcWing 1015. 摘花生(统一模型)
AcWing 275. 传纸条(四维方案,两次)
2.最长上升子序列模型
AcWing 482. 合唱队形
AcWing 1010. 拦截导弹(贪心+dp)
AcWing 187. 导弹防御系统(dfs)
AcWing 272. 最长公共上升子序列(最长上升子序列+最长公共子序列(划分思想)*
3.背包模型:
(背包问题求具体方案 ,求方案数,求最小值,求最大值)
(完全背包 ,01,背包,多重背包,分组背包)+一维优化
(背包问题三种问法:至少是,最多是,至少是)
当所有空间优化成一维后,只有完全背包问题(每个物品可以选无限个),(多重背包问题的单调队列优化也是)的体积是从小到大枚举的 ,其他均是从大到小。
背包问题的一维优化可以参考:
https://www.acwing.com/solution/content/30250/
关于01背包恰好装满的解释:
一 01背包恰好装满问题,要在初始化将数组初始化为负无穷,然后f[0] = 0, 这样可以保证最后的答案是由f[0]转移过来的
二 这里恰好达到m是通过初始化f[0]=1,其余的f[i]=0得到的,
可以保证最后的结果f[m]是由f[0]转移过来的,
如果是从f[i],i不等于0的状态转移,那么最后的结果f[m]始终是0;
如果想要总和是小于等于m,全部的f[i]初始化为1即可。
状态表示:f[i][j]从前i个数字里面选 ,和为j的最多方案数
求最大值最小值初始化总结
二维情况
1、体积至多j,f[i,k] = 0,0 <= i <= n, 0 <= k <= m(只会求价值的最大值)
2、体积恰好j,
当求价值的最小值:f[0][0] = 0, 其余是INF
当求价值的最大值:f[0][0] = 0, 其余是-INF
3、体积至少j,f[0][0] = 0,其余是INF(只会求价值的最小值)(体积是可以小于0的)
一维情况
1、体积至多j,f[i] = 0, 0 <= i <= m(只会求价值的最大值)
2、体积恰好j,
当求价值的最小值:f[0] = 0, 其余是INF
当求价值的最大值:f[0] = 0, 其余是-INF
3、体积至少j,f[0] = 0,其余是INF(只会求价值的最小值)(体积是可以小于0的)
作者:小呆呆
链接:https://www.acwing.com/solution/content/7438/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
再具体请参考:
https://blog.csdn.net/Iseno_V/article/details/100697105
AcWing 423. 采药(典型01背包问题)
AcWing 1022. 宠物小精灵之收服(01背包问题+二维费用背包问题+滚动数组优化+阅读理解)
AcWing 278. 数字组合(01背包恰好装满+方案个数)
AcWing 1019. 庆功会(典型多重背包问题+优化)
AcWing 1020. 潜水员 (二维费用背包+至少的体积)
AcWing 11. 背包问题求方案数(典型01背包求方案数,先反正求,再从前推导)
AcWing 1013. 机器分配(典型分组背包问题+方案数)
AcWing 487. 金明的预算方案(需要打包的分组背包问题+二进制优化)
AcWing 532. 货币系统(完全背包+思维)
AcWing 7. 混合背包问题(三类背包问题+多重背包的二进制优化)
难题:
AcWing 6. 多重背包问题 III(多重背包问题+单调队列优化);
AcWing734. 能量石(01背包问题+贪心)
四,状态机模型;
理解为状态机模型适用于约束很多的dp问题
状态机模型视频::算法提高课 1,4状态机模型:38:25–39
AcWing 1049. 大盗阿福(典型状态机问题)
对比:AcWing 1057. 股票买卖
AcWing 1058. 股票买卖 V
AcWing 1052. 设计密码(kmp+状态机)*
五,状态压缩模型:(难)
对于一般的状态压缩dp来说,需要枚举的位置太多了
我们就可以枚举小一点的集合(如一行,一列)
并且用二进制压缩的方式来进行枚举
普通的dp可能枚举的是更小的集合
但是状态压缩dp枚举的是大一点的集合。
AcWing 1064. 小国王(状态压缩+预处理)
AcWing 292. 炮兵阵地(状态压缩+多项预处理)
AcWing 524. 愤怒的小鸟(状态压缩+重复覆盖)**
六,区间dp:
1.区间dp常用技巧:环形 -》链:
2,区间dp记录方案数:
3,区间dp和高精度结合:
4.二维区间dp
AcWing 1068. 环形石子合并(区间dp+处理环问题);
AcWing 1069. 凸多边形的划分(结合高精度);
AcWing 479. 加分二叉树(记录方案数);
AcWing 321. 棋盘分割(二维区间dp)*
七,树形DP:(理解欠佳)**
一棵树,边权正负不确定,求最长直径,需要用树形DP的方法.
AcWing 1073. 树的中心(两次树形dp,dfs+换根思想);
AcWing 1074. 二叉苹果树(树形dp,经典集合思想—)
AcWing 323. 战略游戏(树形dp+状态机) 类比:没有上司的舞会
都是一种最大独立集问题
AcWing 1077. 皇宫看守(比战略游戏更加复杂的状态机,战略游戏:边,皇宫看守:点)
八,数位DP:
与数学相关的dp,方法统一:
注意:数位dp的记忆化搜索的方法也很实用!!!y总讲述的迭代的方法
固定模式:
1先根据题意预处理f数组
2开dp函数,用vector存下来每一位数
3把每一位数做成两类分支(取0-an-1,取an)
4计算结果
数位dp问题的技巧:
1,先算出所有符合的数
如:需要求从[x,y]的所有满足性质的数的个数
求出1-n中,满足性质的个数,用f[n]存。
[x,y]=f(y)-f(x-1);
2.从树的角度考虑问题(每一位能取什么,…,这一位看成一个节点,那么这个节点可以存在几个分支?每个分支的计算方法?);
AcWing 1081. 度的数量(典型数位DP+树形分析)
AcWing 1082. 数字游戏 (预处理需要dp+树形分析+数位dp)前导0可以直接算
AcWing 1083. Windy数 (预处理需要dp+树形分析+数位dp)前导0需要特判
AcWing 1086. 恨7不成妻***
九,单调队列优化DP
模式:如果求区间窗口最值,就可以使用单调队列优化
最优化问题分析法:
在一个有限集合中求最值或者个数
关于队列的tt=0还是-1问题,应该看s[0]是否需要:
具体参考:1089. 烽火传递(打卡)
https://www.acwing.com/activity/content/code/content/3466874/
AcWing 135. 最大子序和(单调队列优化dp 模板题)
AcWing 1088. 旅行问题(单调队列优化dp+破环成链+前后两边队列优化+理解题意)
AcWing 1087. 修剪草坪(对最终的dp结果公式进行处理,把处理出来的新的函数进行单调队列优化)
AcWing 1091. 理想的正方形(二维单调队列+多数组处理)
十,斜率优化dp:
分析问题–》代码的正确性
优化————》提高代码效率:对代码进行等价变形
维护一个下凸包:
对于斜率不再具有单调性 但是对于x,即(cj)一定是单调递增的
1,因为k不再单调递增,所以对于每一个凸包上的点 都有可能让本次的k取得最小的截距
所以我们不能把前面的节点删除
只能用 二分法来查找:
二分:找到第一个斜率大于k的点
2,插入新节点的时候 :
把队尾不再凸包上的点全部删掉:
具体做法:
新节点同时链接上一个点和上上个点,如果该节点和上一个点连起来的斜率没有上上个点的大
那么我们就删掉该节点的上一个节点
经典例题:
AcWing 302. 任务安排3(典型例题)
AcWing 303. 运输小猫 (应用题)
很棒,有帮助到我,感谢感谢