代码随想录训练营二刷第四十一天 | 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

代码随想录训练营二刷第四十一天 | 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

一、509. 斐波那契数

题目链接：https://leetcode.cn/problems/fibonacci-number/
思路：dp[i]表示f(n)的值，递推公式： dp[i]=dp[i-1]+dp[i-2]，初始化: dp[0]=0, dp[1]=1，dp[i]依赖于dp[i-1]和dp[i-2]故从前往后遍历

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

二、70. 爬楼梯

题目链接：https://leetcode.cn/problems/climbing-stairs/
思路：定义dp[i]为到达第n阶有多少种方法，要想到达第n阶只能从n-i阶或者n-2阶到达，到达第n-1阶有dp[n-1]种方法，到达第n-2阶有dp[n-2]阶方法，那么到达第n阶有dp[n]=dp[n-1]+dp[n-2]种方法。初始化dp[1]=1,dp[2]=2；dp[i]依赖于dp[i-1]和dp[i-2]遍历顺序为从小到大。

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

三、746. 使用最小花费爬楼梯

题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
思路：确定dp[i]含义：dp[i]表示抵达第i个台阶所需要花费的最小代价。要到达第i个台阶需要从i-1或者i-2出发，到达第i-1所需要的最小代价是dp[i-1]到达第i-2所需要的最小代价是dp[i-2]，要从i-1或者i-2到达i需要支付cost[i-1]或者cost[i-2]才能从i-1迈一步或者从i-2迈两步，故递推公式dp[i]=Math.min(dp[i-1]+cost[i-1]，dp[i-2] + cost[i-2])。初始化，dp[0]=0,dp[1]=0，题目说可以直接从0或者1出发，0或者1之前并没有花费的地方，从0或者1往上走，需要支付cost[0]或者cost[1]，符合递推公式。

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