动态规划 ​

什么时候用动态规划 ​

1. 要求你给出达成某个目的的解法个数
2. 不要求你给出每一种解法对应的具体路径

思路分析 ​

• 由 总 --> 分的思路，倒着推，将问题拆解成子问题求解
• 将总问题抽象成函数 f(n)
• 将子问题抽象成函数 f(n-1)
• 那么总问题的解决方法就是 f(n) = f(n-1) + X

这样从 总 到 分 的思考方式是 自顶向下 的思路。

编码实现 ​

实现方式1 - 递归 ​

基于思路分析，我们可以实现一个递归的函数，来解决这个问题。

但递归可能会存在重复计算的问题，所以我们可以使用一个缓存来存储已经计算过的结果，这样就可以避免重复计算。

符合 自顶向下 的思考方式。

实现方式2 - 动态规划 ​

动态规划则恰恰相反，是一个自底向上的过程。它要求我们站在已知的角度，通过定位已知和未知之间的关系(状态转移方程)，一步一步向前推导，进而求解出未知的值。

符合 自底向上 的思考方式。

与 分治 的区别 ​

分治问题的核心思想是：把一个问题分解为相互独立的子问题，逐个解决子问题后，再组合子问题的答案，就得到了问题的最终解。

动态规划的思想和 分治 有点相似。

分治 思想中，各个子问题之间是独立的：比如说归并排序中，子数组之间的排序并不互相影响。

而动态规划划分出的子问题，往往是相互依赖、相互影响的。

什么样的题应该用动态规划来做？我们要抓以下两个关键特征：

• 最优子结构 - 问题的最优解就是子问题的最优解
• 重叠子问题 - 子问题之间有重叠

动态规划问题的分析技巧 ​

• 自顶向下：树形思维模型将帮助我们更迅速地定位到状态转移关系
• 结合记忆化搜索，明确状态转移方程
• 递归代码转化为迭代表达