题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。To do it!
示例1 输入： n = 2，输出： 2
示例2 输入： n = 7，输出： 21
示例3 输入： n = 0，输出： 1
提示： 0 <= n <= 100

题解

此题与上一题斐波那契数列基本一致，唯一不同的是起始状态不同。

青蛙跳台阶问题：f(0) = 1, f(1) = 1, f(2) = 2;
斐波那契数列问题：f(0) = 0, f(1) = 1, f(2) = 1.

记忆递归

class Solution {
    vector<int> ans;
    const int mod = 1000000007;
    int f(int n) {
        if (n < 2) return 1;
        if (ans[n] == 0) ans[n] = (f(n - 1) + f(n - 2)) % mod;
        return ans[n];
    }
public:
    int numWays(int n) {
        ans = vector<int>(n + 1, 0);
        return f(n);
    }
};

时间复杂度：O(n)，空间复杂度：O(n)

动态规划

class Solution {
private:
    const int MOD = 1000000007;
public:
    int numWays(int n) {
        /*
        f(0) = 1, f(1) = 1, f(2) = f(0) + f(1) = 2
        f(1) = 1, f(2) = 2, f(3) = f(1) + f(2) = 3
        f(2) = 2, f(3) = 3, f(4) = f(2) + f(3) = 5
        ...
        */
        if (n < 2)
            return 1;
        int a = 1, b = 1, c = 2;
        for (int i = 3; i <= n; i++) {
            a = b;
            b = c;
            c = (a + b) % MOD;
        }
        return c;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)

矩阵快速幂

class Solution {
private:
    const int MOD = 1000000007;
    // 两个 2 * 2 矩阵 a, b 相乘
    vector<vector<long>> multiply(vector<vector<long>>& a, vector<vector<long>>& b) {
        vector<vector<long>> c{{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
            }
        }
        return c;
    }

    // 2 * 2 矩阵 a 的 n 次幂
    vector<vector<long>> pow(vector<vector<long>>& a, int n) {
        vector<vector<long>> ret{{1, 0}, {0, 1}}; // 初始为单位矩阵 I，任意矩阵 M，I * M = M
        while (n > 0) { // n 以二进制处理，从最后一位往前
            if (n & 1) { // n 的当前位数为 1，就与返回结果相乘（幂次上相加）
                ret = multiply(ret, a); // 这里是一个 *= 操作
            }
            n >>= 1; // 位数 +1
            // n 的当前位数对应的幂次
            a = multiply(a, a);
        }
        return ret;
    }
    
public:
    int numWays(int n) {
        if (n < 2) return 1;
        vector<vector<long>> M{{1, 1}, {1, 0}}; // 矩阵 M
        vector<vector<long>> res = pow(M, n - 1);
        // 矩阵 M 的 n - 1 次幂与 [F(1), F(0)] 相乘的结果的第一行第一列即为 F(n)
        // res 是 2 * 2 的矩阵，[F(1), F(0)] = [1, 1]，所以 F(n) = res[0][0]*F(1) + res[0][1]*F(0)
        return (res[0][0] + res[0][1]) % MOD;
    }
};