概念

可以使用动态规划：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
（1）无后效性：未来与过去无关。
eg：f(n) = f(n-1)+f(n-2) 我们只关心f(n-1)和f(n-2)的值，而不关心值是怎么求出来的。
（2）最优子结构性质：大问题的最优解可以由小问题的最优解推出。

DP为什么会快？
无论是DP还是暴力，我们的算法都是在可能解空间内，寻找最优解。
暴力做法是枚举所有的可能解，这是最大的可能解空间。
DP是枚举有希望成为答案的解。这个空间比暴力的小得多。

设计转移有两种方式：一种是考虑我从哪里来，另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到哪些解。

明确三点：

  1. 目标问题
  2. 状态的定义：opt[n]
  3. 状态转移方程：opt[n]=best_of(opt[n-1]，opt[n-2])

步骤

  1. 求一个问题的最优解，大问题可以分解为子问题，子问题还有重叠的更小的子问题。
  2. 整体问题最优解取决于子问题的最优解（状态转移方程）。
  3. 从上（ 目的地）往下（出发地）分析问题，从下（出发地）往上（目的地）解决问题。
  4. 讨论底层的边界问题。