动态规划，一直是各种算法竞赛中难度较大的题目。在同学接触到动态规划的题目时，对于简单的动态规划问题，同学们常常轻易通过，而对于复杂的动态规划，却没有一个很好的思路，那么我们究竟有没有一种统一的思考步骤来解决动态规划问题呢？
卡哥总结了动规五部曲：
- 确定dp数组及其下标的含义
- 确定递推公式(状态转移方程)
- 确定dp公式初始值
- 确定递推方向（遍历方向）
- 打印dp数组验证
很多同学认为，dp的难，难在不能很好的总结出递推公式(状态转移方程)，但其实这个只是动规里面的一个难点，只需要想清楚了dp数组及其下标的含义，我们在推导递推公式时，也会事半功倍。
此外，为什么要先确定递推公式，再确定初始值呢？这是因为很多时候递归的初始值，常常需要由递推公式来确定要定义哪几项初始值，要由dp数组的下标及其含义来确定具体的值。
最后，如果在做动规时，得出的答案跟预想的不一致，不妨先将每次状态转移后的dp数组打印出来，看看跟自己所想的是否一致。如果一致的话，去检查是否转移方程或者初始化出现问题。如果不一致，去看看哪里的问题可能导致这个不一致。
**509. 斐波那契数 **
这个问题相信很多朋友都做过，这道题是可以用递归很轻易的解决出来的
代码如下:
class Solution {
public:int fib(int N) {if (N < 2) return N;return fib(N - 1) + fib(N - 2);}
};
显然由于递归，时间复杂度是O(2^n)太高了
我们现在来思考动规的做法
- 确定dp数组及其下标的含义 -》 dp[i]表示到斐波那契数的第i项的值
- 确定递推公式(状态转移方程) -》 由于斐波那契数列的每一项，由前两项的和推出 dp[i] = dp[i-1] +dp[i-2]
- 初始化递推公式，由于i由i-1和i-2推出，那么i=1和i=2的值，必须初始化 dp[1] = 1 dp[2] = 1
- 确定遍历顺序 -》 后项由前项推出，所以采取从前向后遍历
- 打印dp数组
代码如下:
class Solution {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}
};
时间复杂度O(n) 空间复杂度O(n)
由于每一轮只维护两个数值，所以也可以用变量的方式保存，减少空间消耗
代码如下:
class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};
时间复杂度O(N) 空间复杂度O(N)
70. 爬楼梯
这道题我们也用递归五部曲分析一下
- 确定dp数组及其下标的含义 -》 dp[i]表示到达第i阶台阶的方法总数
- 确定状态转移方程 -》 由于每次只能爬一阶或者二阶，那么dp[i] = dp[i-1] + dp[i-2]
- 确定初始值 -》由于n从1开始 ， 所以dp[0]无意义，dp[1]根据定义应该等于1，dp[2]应该等于2
- 确定遍历顺序，后项由前项推出，所以从前向后遍历
- 打印dp数组验证
代码如下:
class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;vector<int> dp(2);dp[0] = 1;dp[1] = 2;for(int i=3;i<=n;i++){int tmp = dp[0] + dp[1];dp[0] = dp[1];dp[1] = tmp;}return dp[1];}
};
不难看出这题代码几乎与上题一致，爬楼梯其实就是斐波那契的应用。
时间复杂度O(N) 空间O(N)
746. 使用最小花费爬楼梯
这道题，我们还是用动规五部曲来分析
- 确定dp数组及其下标的含义
dp[i] 表示到达第i层的最小花费
- 确定状态转移方程
根据题目所述可知，第i层，只能由i-1 或者 i-2层走一步得到
那么也就是说，如果想要到达dp[i]的花费最小，就是取到达第i-1层的最小花费 + cost[i-1] 和到达第i-
2层的最小花费 + cost[i-2] -> dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
- 确定初始值， 由于这里i需要由i-1和i-2推出，又n>=1，所以要初始化dp[1] 和 dp[2]
根据题目描述可以选择从第一层或者第二层出发，也就是说到达第一层或者第二层是不需要花费的
所以有dp[1] = 0 dp[2] = 0
-
确定遍历顺序 由前推后 所以从前向后遍历
-
打印dp数组
有了上述分析，我们能够很容易的写出如下代码
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int size = cost.size(); // cost[i]表示在第i层向上跳所需要的花费vector<int> dp(size+2);dp[0] = 0;dp[1] = 0; // dp[i] 表示到达第i层所需要的最小花费for(int i=2;i<=size;i++){dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);}return dp[size];}};