关于DP、递推和递归的区别与优劣
DP对很多新手来说非常可怕，而递推和递归就比较简单。所以，我想给大家分享一下我对这三者的理解与感受。
$(update\ 2022.4.1)$：这篇分享由多次写成，每个部分之间关系不大。这篇分享以后也会持续更新。
DP、递推和递归的区别
首先，让我们不管DP，先了解了解递推和递归。递推在数学中很常用（如杨辉三角、标数法、递推数列等），概念也和数学中的一样，靠循环解决；而 递归就和数学中的递推归纳不同了。在计算机中，递归指像DFS这样的，在函数中自己调用自己的写法（像阿克曼函数）。简而言之，递推就是从小到大一个一个算出结果，最后得到答案。而递归则是从大到小一层一层往下钻，求出算最终答案需要的东西。这两者其实都很简单。
接下来，让我们来看 DP。DP 其实就是 递推和递归的升级版本。递推和递归 中几个维度的变量（如递推数列的下标、上楼梯和标数法的行、列等）都是题目中直接地，明显地告诉了你的；而DP 的维度是我们自己 生造出来的，题目中没有明确说到的（如01背包的序号和体积）。因此，DP 就会比 递推、递归难想，隐蔽许多。同时 DP 也是生造维度情况下 递推和递归的统称。所以，DP 涵盖了 递推和递归的思想。这是它的又一个难点。此外，DP 的每一次递推也可以看成一次 决策。例如，在背包问题中，每一次递推就相当于做了一次选与不选的 决策。
DP、递推和递归的优劣
递推和递归 具体的分析如下图，而 DP 可以类比进行分析。
只要 深度理解了递推和递归（尤其是递推），学习DP就相对轻松 了。
$(update\ 2022.4.17)$：这里插一句，递归不只有类似递推的功能。它在 分析树形结构 等领域也有很大作用。
DP的分类
基本DP
线性DP
背包问题
- 零一背包问题
- 完全背包问题
- 多重背包问题（一二三）
- 混合背包问题
- 分组背包问题
- 有依赖的背包问题
子序列问题
- 最长子序列问题
- 上升子序列问题
- 最长上升子序列问题
数位DP
与 进制 有关的 DP 问题。
区间DP
主要涉及可以 从小的区间往大的区间合并 的问题。一般先枚举区间长度
length，再枚举区间起点l。此时的终点r等于l+length-1。
树形DP
少见的使用 递归 的 DP。
- 有依赖的背包问题
概率DP
求解概率和期望的 DP。一般情况下，求解概率用正推，求解期望用逆推。转移方程较为灵活。
状态压缩DP
普通状压 DP
基于连通性状态压缩的动态规划问题
插头 DP
- 骨牌 DP
- 哈密尔顿路 DP
DP优化
这篇文章 写得非常好。
DP与贪心
DP 和贪心的共同点是它们都是 通过一系列决策来解决问题 的。不同的是，贪心思想中的决策是 不会影响之后的决策 的；而 DP 一般 会影响之后的决策。（这一点，下面的第二个推荐题目可以给你明显的感受）所以，在贪心中，我们每一步都要贪心地 选择最优解，不用保留其他解。而在 DP 里，我们通常要把 所有可能影响最终答案的情况 全部保留。贪心中所做的决策 可能依赖之前的决策，但 不依赖之后的。而 DP 中所做的决策不仅 依赖之前的决策，还取决于 未解决的那部分问题是否有一个较优的解。这也解释了为什么贪心一般比 DP 快以及为什么 能用贪心就不用 DP。
如何解题
说了这么多，该聊聊如何解题了。我将把我的一些方法写在下面：
1st：套
多积累板子，还要背熟；像背包、石子合并这些常用 模板 一定要练会。它们都是你的朋友，在比赛中能 帮助你做出难题！但请千万注意，模板是会变化的。还有，你即使把模板背得滚瓜烂熟，也还是可能做不出题：那些 模板会藏得很深。还是要多刷题。如果没有模板可以套，那就结合 DP 的分类部分，确定题目的类别。
2nd：定
DP的维度是我们自己生造出来的，题目中没有明确说到的。所以，我们如果没有找到适用的模板，就得 先把这些维度生造出来。
3rd：界
无论DP是递推型还是递归型，我们都需要 边界 以及最终需要的 答案。如果你发现边界或答案算不出来，就请你回到第二步吧。
4th：推
知道了边界，我们也要知道 如何用边界一步一步推导答案。当然，如果你发现算不出来，也请回到第二步。
5th：查
检查 算法的 时、空复杂度和优化方法，然后就可以写代码啦~
DP的转移方程
$(update\ 2022.4.18)$：DP的 转移方程（即 递推式）也是一个难点。在这里我也把常见套路整理一下。
转移方程的时间复杂度
在考虑转移方程之前，我们要先计算出它的 时间复杂度。这个不算难（吧？）。具体方法就是：
$$转移时间=\frac{总时间}{递推时间}$$
其中 $1000ms=1s=5\times 10^8次计算$。
一、加法原理
加法原理的核心思想是 分类，也就是把最终的答案分成 不重不漏 的几类，再把不同的情况相加。较为典型的有选第i个和不选第i个（背包）。
未完待续
二、乘法原理
未完待续
三、容斥原理
未完待续
推荐题目
No.1
AcWing.306 杰拉尔德和巨型象棋
这道题，又像递推又像DP，处于他俩的过渡位置。个人建议你先自己稍微想想（但不要太久），然后看看题解。这题非常好理解，适合作为从 递推到DP的过渡。
No.2
AcWing.1054~1059 股票买卖系列
关于这一套题，我主要想让大家思考的是 贪心 与 DP 的区别。这一套题值得大家慢慢体会，可以用来帮助大家理解 DP的原理。
No.3
AcWing.854 Floyd求最短路 算法基础课
Floyd求最短路相关题目 (AcWing)
Floyd求最短路相关题目（洛谷）
这是一个较简单的、用 DP 实现的 最短路模型。用它学习 DP 是非常好的。因为一来它很简单，二来它不需要太多前置知识（最多就邻接表 /邻接矩阵）。它的重点在于理解 为什么可以在一条路中插入任意多个点。大家可以自己好好想想。
No.4
AcWing.885 求组合数二（杨辉三角递推） 算法基础课
这个题的递推式较为明显，即$C_a^b=C_{a-1}^{b}+C_{a-1}^{b-1}$。但是它的 边界 与 循环的模式 较难考虑周全，比较考写代码的仔细程度。
彩蛋
$(update\ 2022.12.18)$：最近刷数竞小蓝本偶遇一堆DP，可见 DP对数竞也有不小帮助。
