DP(Dynamic programming)，动态规划，初次见面，一无所知，一头雾水。到底什么样的问题才算是动态规划问题呢。
从字面上理解，“动态” 就是问题有时间上的变化，问题规模的发展与时间存在一定的关系；“规划”就是问题是可以通过前面的一步一步发展得到的。“动态规划”问题，个人略见，问题规模 n 与时间发展存在一定的关系，也与发展过程 n - i 存在一定的关系。这是我初步理解的 “动态规划” 问题。
而实际的 “动态规划” 问题是与 重叠子问题，最优子结构，状态转移方程 三要素有关的。
看到这个，对 DP 问题更加模糊了，什么才是 DP 呀。
对一种算法的理解，不能单单靠理论知识来理解，这对理解算法是不透彻的。我们需要通过实际的运用来理解 DP 问题。
下面从 LeetCode 的一些问题出发，来理解 DP 问题。
一个数列，第一项和第二项是 1，从第三项开始都是前面两项之和。
要求 Fib(n)，显然我们需要知道前面的 Fib(n - 1) 和 Fib(n - 2)，依次往前推，直到 Fib(0) 和 Fib(1)。我们使用递归方式可以计算出 Fib(n)。
但是这里就有一个问题了，比方说计算 Fib(10)，那么就要求得 Fib(9) 和 Fib(8)；同理计算 Fib(9) 时，就要求得 Fib(8) 和 Fib(7)，很明显这里 Fib(8) 要重复计算两边，进而 Fib(7), Fib(6)... 都要计算两边了。那么这里就可以使用一个 table 把前面计算过的值保存起来，下回计算时直接取出来用就好了。
那么，我们的问题时间复杂度就从 O(2^n) 降到了 O(n)。
这样我们就用到了 DP 的两个属性，重复使用已计算的结果 和 使用 table 降低时间复杂度。
上面的方式使用的是 up-bottom 的方式，同样的我们也可以使用 bottom-up 的方式来计算结果。
既然要求的后面的结果就必须先知道前面的值，那么我们就可以从前面一步一步的往后推算，[1, 1, 2, 3, 5, 8, ...] 直到我们需要求得的结果。这样计算的时间复杂度跟前面 递归+备忘录 的是一样的，只是路子不同而已，一个是 bottom-up，一个是 up-bottom。
Fibonacci 算 DP 问题吗？我还不懂得如何判断一个问题是不是 DP 问题。要判断一个问题是不是 DP 问题，就看它满不满足 重叠子问题 和 最优子结构。Fibonacci 是不满足 最优子结构 的特征的。
但是 Fibonacci 确满足了解决 DP 问题时的一些特性，重复使用已计算的结果 和 使用 table 降低时间复杂度。
DP 问题是有一定的套路的，我需要总结自己的一套思路或者套路。
首先你得判断问题是不是 DP 问题，如果判断不准确直接套用 DP 的套路纯属是浪费时间嘛。
- 判断是否是 DP 问题
- 怎么判断是否是 DP 问题呢
- 重叠子问题
- 最优子结构
- 如果是 DP 问题
- subproblem
- up-bottom的方式 ==> 递归，递归+备忘录
- bottom-up的方式 ==> dp table 定义，（一维、二维、三维，多个dp table）
- resue前面计算的结果
所以问题回到了如何判断一个问题是 DP 问题？
学习算法，我们需要努力的学习其中的道，而不是术。道就是算法背后的思想逻辑，术就是套路模板。