@代码随想录算法训练营第38天 | 动态规划 LeetCode509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯

509. 斐波那契数

第一遍读题思考

确定dp[i]的含义，确定递推公式，如何初始化，确定遍历顺序。

代码随想录解法思路

。

c++代码具体实现注意事项

class Solution {
public:int fib(int n) {if(n<=1) return n;int dp[2];dp[0] = 1;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];}
};

70. 爬楼梯

第一遍读题思考

确定dp[i]的含义，确定递推公式，如何初始化，确定遍历顺序。

代码随想录解法思路

dp[i]就用来表示爬上第i层台阶有几种方法，那么很显然，递推公式就是dp[i]=dp[i-1]+dp[i-2]。

c++代码具体实现注意事项

class Solution {
public:int climbStairs(int n) {int dp[3];dp[0] = 1;dp[1] = 1;if(n<=1) return 1;for(int i=2;i<=n;i++){dp[2] = dp[0]+dp[1];dp[0] = dp[1];dp[1] = dp[2];}return dp[2];}
};

746. 使用最小花费爬楼梯

第一遍读题思考

确定dp[i]的含义，确定递推公式，如何初始化，确定遍历顺序。

代码随想录解法思路

dp[i]就用来表示爬上第i层台阶所耗费的体力，初始化dp[0]和dp[1]等于0，因为爬上0和1台阶不需要消费体力。
那么爬上dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

c++代码具体实现注意事项

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int dp[3];dp[0] = 0;dp[1] = 0;for(int i=2;i<=cost.size();i++){dp[2] = min(dp[1]+cost[i-1], dp[0]+cost[i-2]);dp[0] = dp[1];dp[1] = dp[2];}return dp[2];}
};