代码随想录算法训练营第三十八天 | 509. 斐波那契数 ● 70. 爬楼梯 746. 使用最小花费爬楼梯

代码随想录算法训练营第三十八天 | 509. 斐波那契数 ● 70. 爬楼梯 746. 使用最小花费爬楼梯

一、力扣509. 斐波那契数

题目链接
思路：dp[i] = dp[i - 1] + dp[i - 2]，从前向后

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

一、力扣70. 爬楼梯

题目链接
思路：1楼有1种方法，2楼有两种方法，上3楼只需要在1楼的基础上走2步，在2楼的基础上走1步，所以3楼的方法就等于1楼的方法加2楼的方法，dp[i] = dp[i-1]+dp[i-2]

class Solution {
    public int climbStairs(int n) {
        if (n < 3) return n;
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n ; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

一、力扣 746. 使用最小花费爬楼梯

题目链接
思路：

class Solution {
    public int minCostClimbingStairs(int[] cost) {

        int a = 0, b = 0;
        for (int i = 2; i <= cost.length; i++) {
            int c = Math.min(a+cost[i-2], b+cost[i-1]);
            a = b;
            b = c;
        }
        return b;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12