AcWing——第一章动态规划专题

2020-11-18

一、数字三角形模型:

大致思路:
还记得最早接触 DP 的时候已是大一下学期,当时积累并不够,看待 DP 问题也还只是认为是玄学,为什么要有状态的概念?什么叫做子集划分呢?可惜听 y 总的课太晚了导致自己错过了最好的学习机会,但是这并不是理由,嘻嘻不闲扯了,那么究竟什么是数字三角形模型呢?我将这个模型看待成递推的过程,还记得杨辉三角吗?即下图所示:
image.png

我们不难发现对于任意位置(i,j)那么它是由它上一行同一列即(i-1,j)以及上一行前一列即(i-1,j-1)相加得到的,那么对于数字三角形模型它通常有以下特性:
(1)某一步只能从上一行同一列或者上一行前一列得到的,对应到具体问题中通常是:规定只能向南走或者只能向东走,(上北下南),即当前这个状态(可以看做是当前位置格子里存放的数据)只能更新到它正下方或者正右方,又或者可以说当前这个状态只能从其上方或者左方更新过来。看下图所示:
image.png

(2) 一般定义状态 f(i,j)为走到格子(i,j)时的最大/最小/数量 是多少 这里一定要注意为什么 Dp 能够快速的求解呢? 其实 y 总讲的特别容易理解。Dp 是从集合的角度分析问题,假设 dp(i,j)是所有从(0,0)走到(i,j)的集合,那么假设说(i,j)并没有走到终点,那么我们只需要保留当前路线中的最大值即可,这里的最大值是属性的一种,亦可能是最小值、数量等等。所以通过这样的形式我们将一些路线舍弃掉了,只留下了当前最优的一种方案,再通过这个方案去更新下面的即可。即对应着下图所示的分析过程:
image.png

(3)最近重学 Dp,复习笔记的时候发现了一个之前没有理解到的地方:
我们推出的状态转移方程是:

dp[i,j]=\left\{\begin{matrix} max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; \end{matrix}\right .
本题并没有以当前格子选或者不选作为划分依据,因为走到当前格子的时候是必选状态的,但是有的 Dp 像状态机模型便是会以当前数选或者不选进行划分,这种划分的时候我们需要明白一点:举个形象的例子,像背包问题推出的递推公式是以下形式的:

dp[i,j]=\left\{\begin{matrix} max(dp[i][j],dp[i-1][j-w[i]]+v[i]); \end{matrix}\right.
**所以假设当前这个物品没有被选择的时候那么值一定是之前被计算过的即
dp[i-1][j],因此我们只需要去考虑假设当前物品被选择的时候的方案数中的最大值即可:即 dp[i-1][j-w[i]]+v[i]

习题:

1.1、AcWing 1015 摘花生
1.2、AcWing 1018 最低通行费
1.3、AcWing 1027 方格取数
1.4、AcWing 275 传纸条

二、最长上升子序列模型:

2.1、AcWing 1017 怪盗基德的滑翔翼
2.2、AcWing 1014 登山
2.3、AcWing 482 合唱队形
2.4、AcWing 1012 友好城市
2.5、AcWing 1016 最大上升子序列和
2.6、AcWing 1010 拦截导弹
2.7、AcWing 187 导弹防御系统
2.8、AcWing 272 最长公共上升子序列

三、背包模型:

3.1、AcWing 423. 采药
3.2、AcWing 1024. 装箱问题
3.3、AcWing 1022. 宠物小精灵之收服
3.4、AcWing 278. 数字组合
3.5、AcWing 1023. 买书
3.6、AcWing 1021. 货币系统
3.7、AcWing 532. 货币系统
3.8、AcWing 6. 多重背包问题 III
3.9、AcWing 1019. 庆功会
3.10、AcWing 7. 混合背包问题
3.11、AcWing 8. 二维费用的背包问题
3.12、AcWing 1020. 潜水员
3.13、AcWing 1013. 机器分配
3.14、AcWing 426. 开心的金明
3.15、AcWing 10. 有依赖的背包问题
3.16、AcWing 11. 背包问题求方案
3.17、AcWing 12. 背包问题求具体方案
3.18、AcWing 734. 能量石
3.19、AcWing 487. 金明的预算方案

四、状态机模型:

4.1、AcWing 1049. 大盗阿福
4.2、AcWing 1057. 股票买卖 IV
4.3、AcWing 1058. 股票买卖 V
4.4、AcWing 1052. 设计密码
4.5、AcWing 1053. 修复 DNA

五、状态压缩 DP

5.1、 AcWing 1064. 小国王
5.2、AcWing 327. 玉米田
5.3、AcWing 292. 炮兵阵地
5.4、AcWing 524. 愤怒的小鸟
5.5、AcWing 529. 宝藏

六、区间 DP

6.1、AcWing 1068. 环形石子合并
6.2、AcWing 320. 能量项链
6.3、AcWing 479. 加分二叉树
6.4、AcWing 1069. 凸多边形的划分
6.5、AcWing 321. 棋盘分割

七、树形 DP

7.1、AcWing 1072. 树的最长路径
7.2、AcWing 1073. 树的中心
7.3、AcWing 1075. 数字转换
7.4、AcWing 1074. 二叉苹果树
7.5、AcWing 323. 战略游戏
7.6、AcWing 1077. 皇宫看守

八、单调队列优化 DP

8.1、AcWing 135. 最大子序和
8.2、AcWing 1087. 修剪草坪
8.3、AcWing 1088. 旅行问题
8.4、AcWing 1089. 烽火传递
8.5、AcWing 1090. 绿色通道 177 人打卡
8.6、AcWing 1091. 理想的正方形

九、斜率优化 DP

9.1、AcWing 300. 任务安排 1144 人打卡
9.2、AcWing 301. 任务安排 2119 人打卡
9.3、AcWing 302. 任务安排 3100 人打卡
9.4、AcWing 303. 运输小猫

十、数位 DP

10.1、AcWing 1081. 度的数量
10.2、AcWing 1082. 数字游戏
10.3、AcWing 1083. Windy 数
10.4、AcWing 1084. 数字游戏 II
10.5、AcWing 1085. 不要 62
10.6、AcWing 1086. 恨 7 不成妻

标题:AcWing——第一章动态规划专题
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/11/18/1605708639474.html