【算法笔记】动态规划（DP）_动态规划 dp

动态规划（DP）

• 前言
• 矩阵DP
• • 背包问题
  • • 01背包
    • 完全背包
    • 多重背包
  • 打家劫舍
• 树型DP

---

前言

核心思想：状态转移、记忆化搜索、递推、递归

通过一个简单的例子引入
斐波那契数列

问题描述：根据斐波那契数列的规律求第n个斐波那契数

根据题目，首先小明回忆其规律，$F(n)=F(n-1)+F(n-2)$
小明觉得自己还可以更“精简”这个规律
既然$F(n)=F(n-1)+F(n-2),F(n-1)=F(n-2)+F(n-3)$
那么$F(n)=2F(n-2)+F(n-3)$……
可是越发计算，规律却更复杂了。

原来斐波那契先生总结出的就是最优子结构
很幸运，站在巨人肩膀上的小明不用进行大量穷举总结得出规律
而是直接知道了状态转移方程

于是小明准备简单手推一个结果进行验证，如$F(10)$

自底向上的递推

• $F(3)=F(2)+F(1)$
  • $F(4)=F(3)+F(2)$
    • $F(5)=F(4)+F(3)$
      • ……
      • $F(10)=F(9)+F(8)$

小明开心得发现，原来很轻松就可以递推得到$F(10)$
但是小明太兴奋以至于忘记了$F(8)$的值是多少,于是他去尝试回忆自己还记得哪些值

自顶而下的递归

• $F(8)=F(7)+F(6)$
  • $F(7)=F(6)+F(5)$
  • $F(6)=F(5)+F(4)$
    • $F(5)=F(4)+F(3)$
    • ……

以上不断求子问题的过程，其实就是一个递归的过程

但不同于小明的我们也发现一个非常严重的问题——存在大量重复的计算，即子问题重叠
自然而然的，我们希望有一个“备忘录”对已经计算过的数据进行记录，下次使用时直接取之
这种思想就是记忆化搜索

归纳总结：
对于动态规划的问题解决应该分以下几个步骤完成

1. 进行问题分析，确定“备忘录dp”要记录的内容具体是什么，即$dp[]$表达什么
2. 通过各种穷举尝试写出状态转移方程
3. 发现边界情况

---

矩阵DP

背包问题

首要问题是从具体问题中抽象出：

1. 什么是背包容量
2. 什么是物品重量
3. 什么是物品价值

最朴素的背包问题（01）：

问题描述：假如你是一个小偷，背着一个可装4磅东西的背包。现在有以下三种物品可供你盗窃如何才能盗取最大的收益

物品 价格V 重量W 音响 3000美元 4磅 笔记本电脑 2000美元 3磅 吉他 1500美元 1磅

二维：
$dp[i][j]$ 中 $i$ 代表对于每一件物品进行遍历，$j$ 代表对于背包的每一格容量进行遍历，$dp[i][j]$ 为当前物品和容量下，装入背包的最大价值。
其中二维的意义为物品维度和容量维度

确定完dp的意义之后，开始从上到下，从左到右穷举寻找状态转移方程

0 1 2 3 4 0 0 0 0 0 0 1 0 0 0 0 $max(0,3000)=3000$ 2 0 0 0 $max(0,2000)=2000$ $max(3000,2000)=3000$ 3 0 $max(0,1500)=1500$ $max(0,1500)=1500$ $max(2000,1500)=2000$ $max(3000,2000+1500)=3500$

（第0行可理解为，背包空时的状态；第0列可理解为，背包容量为0时，什么都装不下）
注意因为多加了一行0状态的，所以当前行的物品应该是 $i-1$

第一件物品是音响，3000美元，4磅。
从有效的$[1][1]$开始穷举递推，刚出门就遇到问题，1磅的背包装不下4磅的物品！！！
于是得出第一个条件：$j>=W[i-1]$ 时才能开始讨论对于当前物品，取还是不取。装不下的话，免谈！！！

当穷举递推到$[1][4]$，容量$4\ge 4$可以取音响。于是检查了一下背包，当前背包是空的啊，那肯定取。
其中就隐含了另一个问题，怎么取才能获得当前容量下的最大价值？
这便是第二个条件：$dp[i][j]=max(dp[i-1][j],V[i-1])$，比较当前背包里的物品和当前要取的物品哪个价值更大！！！

根据以上两个条件，一直穷举递推到$[3][4]$。照例，比较当前背包里的物品和当前要取的物品价值，发现 $3000>1500$
但仔细一想，如果取第二件物品笔记本电脑和第三件物品吉他的话，$2000+1500=3500>3000$
原来背包没规定只能装一件物品啊！！！
于是，想到对于第三件物品其实只需要1磅的容量，那另外多出来的空间可以装别的物品啊！！！

多出来的空间为$j-w[i-1]$，其最大价值为$dp[i-1][j-w[i-1]]$
不用怀疑，因为我们每次递推得出的都是当前容量下的最大价值，这递归回去的仍然也是
那么可以对第二个条件进行修改：$dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1])$

由递推和递归，得出完整的状态转移方程
dp[i][j]= { d p [ i − 1 ] [ j ] j = W [ i − 1 ] dp[i][j]=\\begin{cases}dp[i-1][j] \\quad j=W[i-1]\\end{cases} dp[i][j]={dp[i−1][j]j<W[i−1]max(dp[i−1][j],dp[i−1][j−W[i−1]]+V[i−1])j>=W[i−1]​

dp里的i-1是指上一行状态，w,v中的i-1是指当前行物品，这里要注意

---

一维：
观察二维的状态转移方程是否发现——不论哪种情况下，$dp[i][]$总是与$dp[i-1][]$相关
即当前行以上一行为基础，且不与其他行相关

一个大胆的想法随即孕育而出，将二维压缩为一维，将物品维度塌缩

得出新的状态转移方程
dp[j]= { d p [ j ] j = W [ i − 1 ] dp[j]=\\begin{cases}dp[j]\\quad j=W[i-1]\\end{cases} dp[j]={dp[j]j<W[i−1]dp[j−W[i−1]]+V[i−1]j>=W[i−1]​

继续观察二维的状态转移方程——不论哪种情况下，$dp[][j]$总是与$dp[][k],k<=j$相关
说明每一列以之前列为基础，且不与之后列相关

如果继续二维的从左到右的递推方法，必然出现当前物品取多次的情况，于是我们选择不会影响前列的从右到左递推

何为当前物品取多次？
以取第三件物品吉他$(1500,1)$为例：

0 1 2 3 4 3 0 1500

到容量2时，$dp[2]=dp[2-1]+1500=3000$，凭空多取了一件吉他

---

01背包

0和1的意义：对于每一物品，在每一容量下，是否放入

---

01背包最值问题：

// 二维// row是物品数量 col是背包容量// 最大值for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j >= W[i - 1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i - 1]] + V[i - 1]);}}// 最小值时，将 dp 除边界情况外初始化为0x3f3f3f3f

// 一维for (int i = 1; i <= row; i++) {for (int j = col; j >= W[i - 1]; j--) {dp[j] = max(dp[j], dp[j - W[i - 1]] + V[i - 1]);}}

力扣 1049. 最后一块石头的重量 II
本题要点：

1. 将每两块石头一起粉碎的具体过程，抽象为两堆石头一起粉碎。则两堆石头重量的差值即为剩余重量。
2. 如何构建这两堆石头才能使其差值最小？是不是越接近于 所有石头重量之和的一半 $avg=sum/2$ 更好。
3. $w1\to avg,w2\to avg,w1-w2\to 0$
4. 由此得出，背包的最大容量为 $target=avg$，而每块石头的价值所在就是其重量
5. 求出 $target$ 下能够装入的最大价值，则剩余价值为 $sum-2\ast target$

最大容量转化为$sum/2$是比较多的做法

力扣 474. 一和零
本题要点：

1. 容量有两种，分别用于存放0，1
2. 如何处理多容量问题？通常情况下，将dp定义为两维，物品维度和容量维度
3. 因此做法为直接增加一个容量维度，将其拓展为三维 $dp[i][j][k]$
4. 而重量为每个字符串中，0和1的个数。每个字符串价值为1

能否转化为分组背包问题？

---

01背包存在问题

// 二维for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j > W[i - 1])dp[i][j] = dp[i - 1][j] || dp[i - 1][j - W[i - 1]];}}

// 一维for (int i = 1; i <= row; i++) {for (int j = col; j >= W[i - 1]; j--) {dp[j] = dp[j] || dp[j - W[i - 1]];}}

力扣 416. 分割等和子集
本题要点：

1. 求两个子集元素和相同，那么容量 $target=sum/2$
2. 物品的重量和价值均为数字的大小

洛谷 P8742 [蓝桥杯 2021 省 AB] 砝码称重

---

01背包组合问题：

// 二维for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j >= W[i])dp[i][j] += dp[i - 1][j - W[i - 1]];}}

// 一维for (int i = 1; i <= row; i++) {for (int j = col; j >= W[i - 1]; j--) {dp[j] += dp[j - W[i - 1]];}}

力扣 494. 目标和
本题要点：

1. s u m = ∑ i = 0n u m s [ i ] sum=\\sum _{i=0}nums[i] sum=∑i=0​nums[i]
2. 给 $num$ 添加正号或负号，会产生正数或负数，设正数和为$x$，负数和为$y$
3. { x + y = t a r g e t x − y = s u m ⇒ x = t a r g e t + s u m 2 \\begin{cases}x+y=target\\\\x-y=sum \\end{cases} \\Rightarrow x= \\frac{target+sum}{2} {x+y=targetx−y=sum​⇒x=2target+sum​
4. 所以问题转换为，在每个$num$前考虑是否添加正号（01问题），最后有多少种方法算得 $x$（背包容量）
5. 因为每个$num>=0$，所以$sum>=0$，而$target$是由部分$num$添负号得到，可知$sum>=target$
6. 又因为正数和$x>=0$，所以$target+sum$为非负偶数
7. 边界情况： $dp[0][0]=1$。解释为，由0个数相加得到0是成立的，且只有一种情况

以上方法，将原本的添加正号或符号，变成了只考虑如何添加正号，成功构成了二维的背包。
是否能以多维背包的思想求解？但并没有给定正号和负号的容量大小，正号和负号的多少是互相影响的

其实还有一种比较“老实”的方法，就是将负数转化为正数也编入容量当中，即$j=sum+|a|$
eg. $sum=5$，则 $-3$ 转化为正数就是 $5+|-3|=8$

---

完全背包

完全的意义： 每个物品可以不限次数的取多次

完全背包作为01背包的拓展性问题，理解的要点在于
如何实现物品取多次

回想一下，01背包时二维压缩一维的过程，为什么要从右向左？
因为，之前列会影响当前列，而与之后列无关
（已经证实从左向右可以让小偷凭空多偷出一把吉他）

这正是完全背包需要的，用之前列保存是否取了当前物品的状态，并不断叠加。
（01背包中使用 dp[i-1] 是为了读取 是否取了上一件物品的状态）

---

顺序相关情况分析：
在正式开始介绍完全背包各类问题之前，必须要介绍一种特殊情况——物品取的顺序会影响结果
（这种情况多见于完全背包的组合问题，还未对01背包中的顺序相关问题进行分析）

结果来说，是将内外循环调换，即对于dp一列一列的遍历。
不再是一行一行遍历

接下来以一道简单题进行引入：

力扣 70. 爬楼梯

问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

第3个台阶可以由第2个台阶或第1个台阶爬到。
第4个台阶可以由第3个台阶或第2个台阶爬到。
……
可以推导出本题其实是斐波那契数列规律的一个应用
$F(n)=F(n-1)+F(n-2)$
即第n个台阶可以由第n-1个台阶或第n-2个台阶爬到。

// 以斐波那契数列规律推导int q = 0, p = 1, s;for(int i = 1; i <= n; i++) {s = p + q;p = q;q = s;}return s; // s为爬到第n个台阶的方法数目

或者能不能用背包的思想对本题进行求解。（虽然二者都是动态规划）
可以将每个台阶看作背包的每个容量，而上台阶走一步或两步作为物品的挑选
但是，走一步或两步这个动作是可以多次进行的。说明这是一个完全背包问题

在这个基础上，我们对此题进行推广
将问题修改为：每次你可以爬m个台阶。你有多少种不同的方法可以爬到楼顶呢？
（假设1<= m <= 3）

按照之前背包的遍历方式，应该对每种上台阶的方法（1步、2步、3步）遍历
分别求走到第每个台阶的方式有多少

状态转移方程为：$dp[i]+=dp[i-step]i>=step$

// 走到第3个台阶n = 3;vector<int> dp(3 + 1);dp[0] = 1;vector<int> steps = {1, 2, 3};for (int step : steps) {for (int i = step; i <= n; i++)dp[i] += dp[i - step];cout << \"dp[3] = \" << dp[3];

输出：$dp[3]=3$

是否感觉到不对劲，那手推一遍

走到台阶3的方式1+1+11+22+13

明明有4种，那问题出在哪呢？
原来，在这个走法下，如果按上台阶的方法遍历，走过1，就只能走2，再走3。严格遵循了顺序
$2+1$在这种走法下是无法出现的

说明物品取的顺序会影响最终结果

正确的遍历方式：
应该通过对每个台阶进行遍历，相加走到其前一个台阶，前两个台阶……前m个台阶的方法之和
最终走到第n个台阶有多少种方法

for (int i = 1; i <= 3; i++) for (int step : steps)if (i >= step)dp[i] += dp[i - step];

即对顺序影响结果的问题，应该按照列遍历

---

完全背包最值问题：

// 二维for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j > W[i - 1])dp[i][j] = max(dp[i][j - W[i - 1]] + V[i - 1], dp[i][j]); // 这里有区别，是不断叠加当前物品}}// 最小值时，将 dp 除边界情况外初始化为0x3f3f3f3f, 注意可能要判断是否越界

// 一维for (int i = 1; i <= row; i++) {for (int j = W[i - 1]; j <= col; j++) { // 反而是要从左向右dp[j] = max(dp[j], dp[j - W[i - 1]] + V[i - 1]);}}

力扣 322. 零钱兑换
力扣 279. 完全平方数

---

完全背包存在问题：

// 二维for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j > W[i - 1])dp[i][j] = dp[i][j] || dp[i][j - W[i - 1]];}}

// 一维for (int i = 1; i <= row; i++) {for (int j = W[i - 1]; j <= col; j++) {dp[j] = dp[j] || dp[j - W[i - 1]];}}

力扣 518. 零钱兑换 II

力扣 139. 单词拆分
本题要点：

1. 要考虑顺序
2. 用集合作为字典存放单词，用$substr(j,i-i)$判断是否是一个出现在集合中的单词

---

完全背包组合问题：

// 二维for (int i = 1; i <= row; i++) {for (int j = 1; j <= col; j++) {dp[i][j] = dp[i - 1][j];if (j >= W[i])dp[i][j] += dp[i][j - W[i - 1]];}}

// 一维for (int i = 1; i <= row; i++) {for (int j = W[i - 1]; j <= col; j++) {dp[j] += dp[j - W[i - 1]];}}

力扣 377. 组合总和 Ⅳ
本题要点：

1. 要考虑顺序

---

多重背包

暂时搁置

---

打家劫舍

---

树型DP