代码训练营Day.38 | 509. 斐波那契数列、70. 爬楼梯、746. 使用最小花费爬楼梯

509. 斐波那契数列

1. LeetCode链接

509. 斐波那契数 - 力扣（LeetCode）

2. 解法

递归：

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
};

迭代：

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int c;
        for (int i = 0, a = 0, b = 1; i < n - 1; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

70. 爬楼梯

1. LeetCode链接

70. 爬楼梯 - 力扣（LeetCode）

2. 解法

还是斐波那契数列。但是为什么呢？

爬n层楼梯，可以有两种推导：

1. 爬n-1层楼梯的所有方法，再多走一步就是n层了

2. 爬n-2层楼梯的所有方法，再多走两步就是n层了。

所以，f(n) = f(n - 1) + f(n - 2);

746. 使用最小花费爬楼梯

1. LeetCode链接

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

2. 解法

1. bp数组即下标：参照cost数组，bp[i]表示爬到第i阶所需最小花费。

2. 递推公式：bp[i]取决于两种方案，即（爬到i - 1阶所需最小花费）bp[i - 1] + （从i - 1阶走一步）cost[i - 1]和（爬到i - 2阶所需最小花费）bp[i - 2] + （从i - 2阶走两格）cost[i - 2]中最小的那一个。

3. bp数组初始化：bp[0] = 0、bp[1] = 0；

4. 遍历顺序：顺序遍历；

5. 举例推导：略

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