代码随想录算法训练营Day33 | 509. 斐波那契数 | 70. 爬楼梯 | 746. 使用最小花费爬楼梯
今日任务
509. 斐波那契数
- 题目链接： https://leetcode.cn/problems/fibonacci-number/description/
- 题目描述：
Code
class Solution {
public:int fib(int n) {if(n == 0 || n == 1){return n;}int f0 = 0, f1 = 1;for(int i = 2; i <= n; i++){int newf = f0 + f1;f0 = f1;f1 = newf;}return f1;}
};
70. 爬楼梯
- 题目链接： https://leetcode.cn/problems/climbing-stairs/
- 题目描述：
Code
class Solution {
public:
int climbStairs(int n) {
// vector memo(n + 1, -1);
// function<int(int)> dfs = [&](int i)->int{
// if(i <= 1){
// return 1;
// }
// int &m = memo[i];
// if(m != -1){
// return m;
// }
// return m = dfs(i - 1) + dfs(i - 2);
// };
// return dfs(n);
int f0, f1;f0 = f1 = 1;for(int i = 2; i <= n; i++){int newf = f1 + f0;f0 = f1;f1 = newf;}return f1;
}
};
746. 使用最小花费爬楼梯
- 题目链接： https://leetcode.cn/problems/min-cost-climbing-stairs/description/
- 题目描述：
Code
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// vector<int> memo(cost.size() + 1, -1);// function<int(int)> dfs = [&](int i)->int{// if(i <= 1){// return 0;// }// int &res = memo[i];// if(res != -1){// return res;// }// return res = min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2]);// };// return dfs(cost.size());int f0 = 0, f1 = 0;for(int i = 2; i <= cost.size(); i++){int newf = min(f0 + cost[i - 2], f1 + cost[i - 1]);f0 = f1;f1 = newf;}return f1;}
};