Dynamic Programming
1.浅谈动态规划
- 这是一种适用于解决可递归问题的优化方法，这里的递归涉及到了分治（转为子问题）的思想。
注意区分动态规划与分治：
- 分治的子问题一定是相互独立的，即它分出来的每个子问题都可以作为一个独立的问题，而动态规划的子问题不一定相互独立
- 动态规划的子问题存在重叠部分，即不同的子问题可能会多次使用相同的中间结果；而分治的子问题之间相互独立，不存在重叠的部分。
- 动态规划相对于普通的暴力遍历方法的优化之处在于：它运用了历史记录，即通过记忆数组来存放会重复用到的结果
2.动态规划的步骤
- 赋予数组元素的含义：上文所说，动态规划会用到记忆数组，这个记忆数组dp[]是我们自己定义的，所以要赋予dp[i]特定的语义
能否准确地定义好你的记忆数组dp[]常常是我们能否能准确切入题目的关键
- 找出数组元素之间的关系式：当我们要计算dp[n]时，它可能和dp[n-1]和dp[n-2]这类子问题有关，找出它们的最优关系式即可求解dp[n]
注意：上述子问题可能组合成多种不同的表达式来表达dp[n]，所以我们一开始可能要列出很多表达式，然后逐一分析去寻找那个最优的来最终表达我们的dp[n]
- 找出初始值：对于每个适用于dp算法的问题，我们都能不通过dp算法求出初始的一个或多个值
你可能会纳闷：到底哪些是初始值呢？一般来说：对于一维数组，是dp[0]和dp[1]这种前几个的情况；对于二维数组来说，一般是dp[0][0……n-1]和dp[0……n-1][0]这种边界情况
3.具体解法思路
- 带备忘的自顶向下法：我们从父问题开始，逐步向下求解对应的子问题时，我们先查看记忆数组里这个子问题的解是否被放进去了，如果有，那么直接套用这个解就不必再求这个解了，如果没有，则再把这个子问题分解成几个孙问题来求，求出的过程中我们不仅有了这个子问题的解，也会求出几个孙问题的解，把它们都放入记忆数组中即可
- 自底向上法：我们从最底层的子问题开始逐步向上求解。在求解父问题的过程中，我们就可以直接在它的表达式里直接套用之前以前求过的子问题的解
二者的区别：前者是把一部分（实际表达式中会用到）的子问题求出来并放入记忆数组中；而后者则是把所有的子问题都求出来并放入记忆数组中
- 重构解：将原来的记忆数组升级成记忆结构体，结构体中有两个数组，一个是原来的记忆数组，另一个是存储分解方法的数组。具体方法和前文没什么区别，只不过在放入记忆数组的时候同时把当时的分解方法存入那个存储数组。
光说不练假把式，下面看一下一些很经典的案例
4.经典案例（由于篇幅有限，本文故不详细讲解每题，具体的解法大家可以自行上网查询）
- 青蛙跳台阶：简单的一维问题
- 网格坐标移动：简单的二维问题
- 网格坐标移动升级版（考虑路径代价最小）：较复杂的二维问题
- 单词转换（考虑操作代价最小）：比较难的二维问题
本题由于操作的不同，所以dp[n]有多种表达式，这时需要我们分情况讨论，然后选出那个最优子结构
- 数字三角形（路径代价最小）：有意思的二维问题（生动形象的自顶向下和自底向上方法运用的案例）
- 钢管切割问题（售价最高）：经典的一维问题
