DP 基本有两个模板：
自上而下：先有最初的结果，求出最后的结果。
Paste_Image.png
自下而上： 先有最后的结果，然后求出最初的结果。
Paste_Image.png
什么情况下适合用动态规划呢：
- Counting ( 例如coing change problem, 给出 固定的 amount 和不同的硬币，然后算出有多少的方法）
- 计算最大值，最小值（其实这个和counting 很像的，就是counting 出来后选出最大或者最小值）
- Yes/No 问题。
动态规划的4个要点：
- 有状态转移 （这个状态的转移的sub-problem 是一样的）
- 方程 （就是转移方程，例如方程是以 2% 的概率转移到另一个状态的）
- 初始化 （最初的状态是什么）
- 最终的状态 （最终状态）
这个状态可以是从最后到开始，也可以从最开始到最后。
DP 题目总结：
1.Matrix Dynamic Programming:
- Sequence Dynamic Programming
- Two Sequence
- Backpack
网友评论