动态规划解题大纲

思考方向

对于动态规划的题，可以分为五步去思考：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

入门题目《斐波那契数列》

1. 确定dp数组以及下标的含义
   dp[i] = 第 i 个斐波那契数的值

2. 确定递推公式
   斐波那契数的定义即为递推公式，即 dp[i] = dp[i-1] + dp[i-2]

3. dp数组如何初始化
   斐波那契数已经假设 dp[0] = 0; dp[1] = 1

4. 遍历顺序
   由递推公式可知，若要求解 dp[i] 需要先知道 dp[i-1] 和 dp[i-2] 的值
   所以遍历顺序应该为 从前往后

5. 举例推导dp数组（重要）
   根据定义，自己先在纸上算出斐波那契数列的前几个值。
   随后编写程序，用程序求解得到dp数组，打印dp数组，检查dp数组是否与自己的预期值是否有偏差。
   当发现自己的程序有错误无法AC时，可以通过第五步来Debug程序，以确认是第几步出现了问题