DP笔记(15)：递推型动态规划概念性总结
Author：zhoulujun Date：
DP对很多新手来说非常可怕，而递推和递归就比较简单。
递推型动态规划
动态规划是一种求最优化递推问题，动态规划中涉及到决策过程； 所以动态规划是递推问题的子问题。
让我们不管DP，先了解了解递推和递归。
前置知识：
递推在数学中很常用，概念也和数学中的一样，靠循环解决（如杨辉三角、标数法、递推数列等）；
递归就和数学中的递推归纳不同了。
在计算机中
递归指像DFS这样的，在函数中自己调用自己的写法（像阿克曼函数）。简而言之，递推就是从小到大一个一个算出结果，最后得到答案。
递归则是从大到小一层一层往下钻，求出算最终答案需要的东西。这两者其实都很简单。
DP 其实就是 递推和递归的升级版本。递推和递归 中几个维度的变量（如递推数列的下标、上楼梯和标数法的行、列等）都是题目中直接地，明显地告诉了你的；而DP 的维度是我们自己 生造出来的，题目中没有明确说到的（如01背包的序号和体积）。因此，DP 就会比 递推、递归难想，隐蔽许多。同时 DP 也是生造维度情况下 递推和递归的统称。所以，DP 涵盖了 递推和递归的思想。这是它的又一个难点。此外，DP 的每一次递推也可以看成一次 决策。例如，在背包问题中，每一次递推就相当于做了一次选与不选的 决策。
数学归纳法：
验证k0 成立； （边界条件）
证明如果ki 成立，那么Ki+1 也成立；（推导公式）
联合a & b, 证明k0 -> kn 成立；
递推问题的步骤：
确定递推公式时候，不要管前一个结果如何得到
确定递推状态（状态方程，学习重点）： 一个函数符号f(x), 以及函数符号的含义描述； 确定自变量x（影响结果的因素有哪些）, 因变量y;
确定递推公式（ki -> ki+1) ，取决于递推状态的定义；（这里ki 是第i组对应的满足题意的结果，不要纠结与它怎么得到的！）
分析边界条件；
程序实现： 递归 或者 循环
递推 与 动态规划 之间的关系：
a. 动态规划是一种求最优化递推问题，动态规划中涉及到决策过程； 所以动态规划是递推问题的子问题；
其中 递推公式 在动态规划中叫做 状态转移方程， 具体步骤与上面递推是类似的；
b. 在状态转移方程中，主要下面三个重点：
状态定义：
决策过程：从所有可能中选择最优解； //如果不涉及决策，大概率就是贪心算法；
阶段依赖：当前阶段只依赖上一阶段； 对于不同问题中，阶段概念是一个很宽泛的定义；
c. 在实际求解问题过程中，有两种方向：处理问题中，如果从哪里来的条件判断比较复杂，那就可以考虑到哪里去的方法；
从哪里来：当前状态 = f(前一个状态 ) ； 当前这个状态(被推导) 可以通过其他状态推导得到；
到哪里去：每更新当前状态时 ==> 主动更新可以从它推导出状态的结果； 当前这个状态(去推导)可以到达哪些状态；
这两种方向，本质是一样的，底层是一个图的结构， 而递推(动归) 求解顺序就是状态依赖图的一个拓扑序，对有向图的一维化序列化的结果；
d. 动归典型题： 体会从哪里来，到哪里去的精髓；
DP、递推和递归的优劣
递推和递归 具体的分析如下图，而 DP 可以类比进行分析。
只要 深度理解了递推和递归（尤其是递推），学习DP就相对轻松 了。
为什么不用递归？
当我们在递归地寻找每个子问题的最优解的时候，有可能会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。
去掉重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了。
解决动态规划问题的核心
解决动态规划问题的核心是找出子问题及其子问题与原问题的关系。
动态规划算法中关于最优子结构和重复子问题的理解的关键点：
证明问题的方案中包含一种选择，选择之后留下一个或多个子问题；
设计子问题的递归描述方式；
证明对原问题的最优解包括了对所有子问题的最优解；
证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）。
解决动态规划问题的步骤
动态规划有两种计算顺序，一种是自顶向下的、使用备忘录（记忆化）的递归方法，一种是自底向上的、使用DP数组（滚动数组）的循环方法。不过在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的DP数组。同时备忘录方法的空间复杂度会比较高。
自顶向下
递归的解法需要非常多的重复计算，如果有一种办法能避免这些重复计算，可以节省大量计算时间。记忆化就是基于这个思路的算法。在递归地求解子问题f(1)，f(2)... 过程中，将结果保存到一个表里，在后续求解子问题中如果遇到求过结果的子问题，直接查表去得到答案而不计算。
自底向上
有了状态转移方程，我们就知道如何从最小的问题规模入手，然后不断地增加问题规模，直到所要求的问题规模为止。在这个过程中，我们可以从小到大记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法，由于避免了递归，这是一种更好的办法。
但是迭代法需要有一个明确的迭代方向，例如线性，区间，树形，状态压缩等比较主流的动态规划问题中，迭代方向都有相应的模式。但是有一些问题迭代法方向是不确定的，这时可以退而求其次用记忆化来做。
动态规划自底向上的四个解题步骤是：
定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序
空间优化（可选）
常见递推关系式
常见状态
坐标型
前缀划分型
前缀匹配型
区间型
背包型
坐标型
dp[i]：从起点到坐标 i 的最值/方案数/可行性
dp[i][j]：从起点到坐标 i, j 的最值/方案数/可行性
前缀划分型
dp[i]：前 i 个字符的最值/方案数/可行性
dp[i][j]：前 i 个字符划分为 j 个部分的最值/方案数/可行性
前缀匹配型
dp[i][j]：第一个字符串的前 i 个字符匹配上第二个字符串的前 j 个字符的最值/方案数/可行性
区间型
dp[i][j]：区间 i-j 的最值/方案数/可行性
背包型
dp[i][j]：前 i 个物品里选出一些物品组成和为 j 的大小的最值/方案数/可行性
常见递推关系式
动态规划虽然飘逸，但还是有规律可循，前人还是总结了好几种常见的递推关系模式。
动态规划算法有三个要素：
所有不同的子问题所组成的表（它包含的问题数目称为问题的大小，即 size）；
问题解决的依赖关系可以看成是一个图；
填充子问题的顺序（实际上就是（2）所得到的图的一个拓扑排序）。
关系具体推荐阅读《动态规划三：常见状态与常见递推关系式》
参考文章：
只要 深度理解了递推和递归（尤其是递推），学习DP就相对轻松 了。 https://www.acwing.com/blog/content/12717/
递推与动态规划 https://www.cnblogs.com/ChunboBlog/p/16094011.html
【力扣刷题】动态规划问题的思考与总结 https://star2dust.github.io/post/leecode-dynamic-programming/
转载本站文章《DP笔记(15)：递推型动态规划概念性总结》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9141.html