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

提示

---

一、斐波那契数

当前数值等于前两个数值相加

class Solution {
public:
    int fib(int n) {
        //1.确定dp数组及含义
        //2.确定递推公式
        //3.dp数组如何初始化
        //4.遍历顺序
        //5.举例推导递推公式
        if (n <= 1) return n;
        vector<int>f(n+1);
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、爬楼梯

1.确定递推公式，爬i-1层楼梯，有dp[i-1]种方法，爬i-2，有dp[i-2]种方法，可以迈一步或者两步到i阶，所以爬到i层有dp[i-1]+dp[i-2]种方法，不是需要迈几步到i阶，而是有几种方法。从i-2层可以迈两步上来，而到达i-2层有dp[i-2]种方法，同理i-1。

class Solution {
public:
    int climbStairs(int n) {
        //1.确定dp数组即下标含义
        vector<int>dp(n+1);
        
        //2.确定递推公式
        if (n <= 2) return n;
        //3.dp数组如何初始化
        dp[1] = 1;
        dp[2] = 2;
        //4.遍历顺序
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、使用最小花费爬楼梯

思路类似与爬楼梯，可以选择迈一步或者迈两步，在这道题中，需要求最小花费，所以需要从能到i层的方法中找出花费最少的，也就是min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //1.确定dp数组及下标含义
        vector<int>dp(cost.size() + 1);
        //2.递推公式

        //3.dp数组初始化
        dp[0] = 0;
        dp[1] = 0;
        
        //4.遍历顺序
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

总结

楼梯和最小花费爬楼梯有点绕，理解了就好很多。
学习时间90min。
学习资料：《代码随想录》。