动态规划五步曲
1.确定dp及dp[i]的含义
2.找出递推公式
3.确定dp数组如何初始化
4.确定遍历顺序
5.打印dp数组验证
一、斐波那契数列
思路：动态规划解法
动态规划五步曲：
1.确定dp及dp[i]的含义
2.找出递推公式
3.确定dp数组如何初始化
4.确定遍历顺序
5.打印dp数组验证
- 1.dp及dp[i]的含义：
根据题目要求，要求出第n个斐波那契数列，那么第i个斐波那契数为dp[i] - 2.递推公式：
dp[i] = dp[i-1] + dp[i-2] - 3.初始化：
dp[0] = 0,dp[1] = 1 - 4.确定遍历顺序
由递推公式可知，第i个斐波那契数是由第i-1和第i-2个得来的。
所以需要从前往后遍历。 - 5.打印出dp数组验证递推公式是否正确
在题解中打印即可。
0 1 1 2 3 5 8 13 21 34 55…
具体代码如下：
class Solution { public: //动态规划解题五步骤 //1.dp数组及其下标的含义 //dp数组是记录斐波那契数列每一个数字，下标i对应第i个 //2.递推公式 //dp[i] = dp[i-1] + dp[i-2]; //3.如何初始化dp数组 //dp[0] = 0,dp[1] = 1 //4.确定遍历顺序 //从前往后遍历 //5.举例推导dp数组 int fib(int n) { if(n<2) 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)
二、爬楼梯
思路：动态规划
动态规划五步曲：
1.确定dp及dp[i]的含义
2.找出递推公式
3.确定dp数组如何初始化
4.确定遍历顺序
5.打印dp数组验证
- 1.由题意可知，爬1个楼梯有1种方法，怕2个楼梯由2中方法。
那么爬i个楼梯有dp[i]种方法。
- 2.递推公式
很明显我们可以知道，要爬第i个楼梯，一定只有两种情况：
- （1）从第i-1个楼梯往上爬1阶
- （2）从第i-2个楼梯往上爬2阶 则爬到第i-1个楼梯上，有dp[i-1]种方法，爬到第i-2个楼梯上，有dp[i-2]种方法 所以：dp[i] = dp[i-1] + dp[i-2]
- 3.dp数组初始化，由递推公式，任意一阶楼梯都是由它前两个得来的。
所以所有楼梯都要从第一阶和第二阶开始。
dp[1] = 1,dp[2] = 2；对于第0阶楼梯，没有意义。
- 4.遍历顺序
从前往后遍历
- 5.打印dp数组即可
0 1 1 2 3 5 8 13 21 34 55…
具体代码如下：
class Solution { public: //动态规划五部曲 //1.确定dp以及dp[i]的含义 //dp[i]：爬到第i层楼梯有dp[i]种方法 //2.确定递推公式 //dp[i] = dp[i-1] + dp[i-2] //3.如何初始化 //dp[0]无意义，不初始化，dp[1] = 1,d[2] = 2; //4.如何进行遍历 //由递推公式可知，第dp[i]是由dp[i-1] 和dp[i-2]得来的，所以需要从前往后遍历 //5.打印dp数组出来验证结果 int climbStairs(int n) { if(n < 3) return n; vector<int> dp(n+1); dp[1] = 1,dp[2] = 2; for(int i = 3;i<=n;++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };
时间复杂度O(n),空间复杂度O(n)
三、使用最小花费爬楼梯
思路：动态规划
动态规划五步曲：
1.确定dp及dp[i]的含义
2.找出递推公式
3.确定dp数组如何初始化
4.确定遍历顺序
5.打印dp数组验证
根据题意可以知道，我们可以选择从下标为0或者下标为1的台阶开始爬楼梯，不管选择哪个，都不消耗体力，只有往上爬的时候才会消耗当前下标i的体力值cost[i]。
很明显我们可以知道，要爬第i个楼梯，一定只有两种情况：
- （1）从第i-1个楼梯往上爬1阶
- （2）从第i-2个楼梯往上爬2阶
从第i-1个楼梯往上爬，需要花费的体力值为：cost[i-1]
从第i-2个楼梯往上爬，需要花费的体力值为：cost[i-2]
我们只需要分别求出到第i-1层的体力dp[i-1]+cost[i-1]和到第i-2层的体力dp[i-2]+cost[i-2]
取最小值即可。
那么，根据动态规划五步曲：
- 1.确定dp及dp[i]的含义：
dp[i]表示爬到第i阶楼梯支付的体力值为dp[i]
- 2.递推公式
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
- 3.如何进行初始化
由于选择楼梯不消耗体力，则dp[0] = 0,dp[1] = 0
（请看dp[i]的含义，是体力值）
- 4.如何进行遍历
由递推公式可知，我们需要从前往后遍历
- 5.打印出dp数组
具体代码如下：
class Solution { public: //动态规划五部曲： //1.确定dp及dp[i]的含义 //dp[i]:到达第i个位置的最小花费为dp[i] //2.递推公式 //dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]); //有dp[i]的含义可知，dp[i-1]的含义是到达第i-1个位置的最小花费。 //3.如何初始化 //我们可以选择从0或者1的台阶开始爬楼梯，说明选择任意一个楼梯是不花费体力的。所以dp[0] = 0,dp[1] = 1; //4.如何进行遍历 //由递推公式可知，遍历应该从前往后遍历。 //5.打印dp数组验证递推公式是否正确 int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n+1); dp[0] = 0,dp[1] = 0; for(int i = 2;i<=n;i++) { dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); cout << dp[i] << endl; } return dp[n]; } };
时间复杂度O(n),空间复杂度O(n)
总结
今天开始学习动态规划算法，收获颇丰。
