动态规划入门
基本概念
首先来介绍一下动态规划问题的基本概念。
1.base case 是表示该问题最简单的形式是什么样的。
2.dp数组(函数) 中的相应变量的值（应变量的的返回值）用来表示该问题的子问题的答案。其中的变量代表着该变量所对应的子问题。
3.状态转移 是指从一个状态到另一个状态转换的方式。不同变量所对应不同的状态，它们的转换方式用状态转移方程来表示。
4.状态选择 对应状态转移中“从哪个状态转移”的问题。通常来讲，动态规划基本上是求最优值问题。所以状态选择，通常都是“从不同状态的状态转移”中选择最优值来作为选择的结果。
5.状态压缩 是指对dp数组（函数）中不同变量的数目进行压缩，以此减少状态的数量，优化算法。
动态规划的必备条件：
1.重叠子问题 是指重复计算的相同状态（拥有相同变量的dp数组中的值或者dp函数所对应的返回值）的子问题。
2.最优子结构 是指能够通过子问题的最优解求出整个问题的最优解。要符合“最优子结构”，子问题间必须互相独立（不同子问题之间不能有制约关系）。
自顶向下解法（递归求解）
自顶向下的解法是指画出递归树的顺序，即从顶点依次画出整个递归树。求解的总问题依赖于子问题的求解，通过递归栈画出整个递归树，再由底层的叶子节点倒推到顶节点，完成总问题的求解。
该方式思路相对简单，符合我们的正常思路。但是传统的递归求解，会带来许多重叠子问题，带来了不必要的计算。所以在传统的递归求解中添加备忘录，记录已经求解过的不同子问题的答案，避免重复计算。
自底向上解法（dp数组的迭代解法）
同理可知，自底向上是指从最简单、规模最小的问题入手，反推出总问题的答案，这种方法与上述方法具体实现方式一致，都是从叶子节点倒推出总问题的答案。对比递归求解，该方法能够减少递归栈的空间开支，优化了算法。
简单模板
1 | # 初始化base case |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ae86's Blog！
