动态规划
这篇文章，包括之后一系列的蓝桥杯文章都是在学习了代码随想录的公开内容之后的个人总结。
十分推荐代码随想录这个网站，里面有不少信息竞赛的相关知识。虽然不是针对竞赛，但大部分内容是一样的，而且讲得很细。其在B站也有视频：代码随想录个人主页-哔哩哔哩视频。
1 动态规划5步曲
动态规划，可以看作是递推的一个推广。因此，一个问题能否用动态规划问题解决，需要看这个问题能否被分解为一个递推问题。具体来说，可以考虑如下的问题：
- 能否分解为子问题？
- 子问题与原问题是什么关系？
当然，有的问题不一定一眼能看出来，我的习惯是先带入dp的方法来看，如果定义的dp数组可以写出递推公式，那大概率就可以用dp做。
基本上，所有的dp问题的解决方法都可以归纳为如下的5步（来自代码随想录）：
- 明确dp数组的定义；
- 找递推公式；
- dp的初始化；
- 遍历顺序；
- 打印dp数组。
我自己在此基础上修改了一些，变成了下面的这 5 步：
- dp定义；
- 递推公式；
- 结果形式（最后的输出是什么？是一个值还是一个等式）；
- 初始条件；
- 遍历顺序。
经典问题一般有一个固定的模板（除了普通dp），这些模板的意义在于让我们看到这个问题之后能够较快的反应过来。 但如果没有按照5步曲来做，没有理解5步曲里每一步在具体问题里的具体含义，背模板只能是表面上的会，如果题目变一下就不会做了。
2 普通dp
在力扣上的dp入门题如下：
这类dp问题的难点在于，分析出这些问题可以用dp，并正确写出dp数组的定义。 如果有了dp数组的定义，后续的5步曲就相对容易了一点。
比如96 不同的二叉搜索树， 考虑一个相对一般的n，比如n=3， 当我们选择一个元素作为二叉搜索树的root后，其方案数就变成了子树方案数的排列组合， 因此原问题就分解为了一个相同的子问题。
3 背包问题
背包问题最明显的特征是取数，在一个集合里取数。
3.1 01背包
简单描述：
有n个物品，每个物品有价值value和体积weight。我们需要选择一些物品到一个固定容量的背包，每个物品只能选择一次。问最大价值是多少。
3.1.1 基本解法
step1，dp数组定义
对于经典的01背包问题，可以定义dp数组dp[i][j]，含义是从第1个物品到第i个物品（根据数组的下标也可能是从0到i），当背包容量为j时的装的最大价值。
step2，递推公式
假设当前是第 i 个物品，当前可用容量为 j ，现在有2种情况：
- 不选第 i 个物品，那么最大价值就是上一个的最大价值：
dp[i-1][j]； - 选第 i 个物品，那么就需要在上一个的最大价值（
dp[i-1][j]）的基础上承受weight[i]的代价（体积），价值则增加了value[i]，即dp[i-1][j - weight[i]] + value[i]
也就是下面的公式：
step3，初始化
现在的 dp 数组是一个二维数组，每一个值都由它正上面相邻的格子和正上方格子左侧的格子推导而得， 因此我们需要初始化第 1 行和第 1 列。
第 1 列的含义是：当可用容量为 0 时的最大价值。显然为 0。
第 1 行的含义是：对于第 1 个物品，容量为 j 时的最大价值。
如果 j 比 weight[0] 小，那一定是 0。而 j 比 weight[0] 大的所有格子，都应该为 value[0]。
step4，遍历顺序
根据我刚才的图片，
- 对于物品：只能从小到大。
- 对于容量：可以从小到大，也可以从大到小。
- 对于物品和容量之间：可以交换。
具体的原理手动模拟一遍就可以了，不过多解释。
3.1.2 状态压缩
从刚才的遍历就可以发现，当前行只依赖于上一行，而且对右上角没有依赖。因此可以状态压缩。
压缩后，dp 就成了 dp[j]。需要注意的是，此时的遍历顺序就固定了，没有可以交换的部分，即外层：物品从小到大，内层：容量从大到小。
- 内外无法交换：只有行间是相邻的依赖，列与列之间的依赖跨行了。
- 内层只能从大到小：行首的值会被行尾的用，因此只能先改行尾，再改行首。
3.1.3 变体
01背包常见的问法（变体）：
- 尽量装满容器，求最大价值（当物品价值等于物品体积，就成了最多能装多少体积）；
- 能不能装满容器；
- 尽量装满容器的方案数。
01背包问题，在容量上有这样的关系：
如果物品的价值等于其自身的体积，那么背包问题求的最大价值就等价于求最大体积。
Leetcode 416.分割等和子集
这题可以看作一个01背包问题，让$sum/2$的背包的最大价值（也即最大体积）等于$sum/2$，则式$\mathrm{(2.2.1)}$的等号取等，则说明有分解方案。3.2 完全背包
完全背包， 之于 01 背包，最大的区别就在于其没有物品数量上的限制。 在理解了基本的动态规划 5 步和 01 背包问题后，完全背包相对而言就很简单了。
代码随想录的视频里说，区别就在：一维数组内层遍历的顺序改为从小到大。 在这里，代码随想录里有解释为什么，但他用的是一维数组举的例子。 我还是喜欢先用二维数组进行理解，而且我觉得二维数组更接近问题的本质一些。
在二维中， 递推公式是：
这个公式表示，当前 dp 数组的值可以从这两个地方更新：
- 当前物品一个都不选，则来自 $\mathrm{dp}[i-1][j]$，
- 当前物品要选，但不知道选多少个。则来自 $\mathrm{dp}[i][j-\mathrm{w}[i]]$。
为什么当前不知道选多少个时可以从 $\mathrm{dp}[i][j-\mathrm{w}[i]]$ 更新？这是其实是把问题给分解了。 我们在考虑 dp 递推公式时，考虑的是一个子问题，而不是一些子问题的组合。
比如以上面的图为例，当前的子问题和 01 背包问题的子问题很像，都是看：选第 i 个物品而容量为 j 时的价值如何从相邻的状态里获得。
在 01 背包和完全背包中，dp数组的定义没变， 但 01 背包中，左边的箭头是从左上到右下，是因为当前物品只能选一次， 如果要选物品 i ，那么选之前的状态只能是 还没有选物品 i 的，也就是 i-1。
而在完全背包中，如果要选物品 i ，那么选之前的状态可能来自 还没选 ，也可能来自 选了一个，又想选一个。同时，选了一个，又想选一个 的状态已经把 还没选 的状态也包括了，也就是 $\mathrm{dp}[{\color{red}i}][j-\mathrm{w}[i]]$ 包括了 $\mathrm{dp}[{\color{green}i-1}][j-\mathrm{w}[i]]$，因此箭头直接变成了从左向右。
如果理解了这个，也就不难理解为什么状压之后内层（背包容量）的遍历顺序是正向的了。
另外，当问题是求最大价值时，内层和外层可以交换遍历顺序。如果是其它的（如组合数，或排列数），则不一定能交换，需要具体分析。