剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57xs06/

递归

class Solution {
    // 用于缓存计算结果，防止重复计算
    int[] catchs = new int[100];
    // 此题与斐波那数列解法相似，设跳上 n 级台阶一共有 f(n) 种跳法，则 f(n) = f(n - 1) + f(n - 2)
    // 而 f(0) = 1, f(1) = 1
    public int numWays(int n) {
        if (n <= 1) return 1;
        if (catchs[n - 1] == 0) catchs[n - 1] = numWays(n - 1);
        if (catchs[n - 2] == 0) catchs[n - 2] = numWays(n - 2); 
        return (catchs[n - 1] + catchs[n - 2]) % 1000000007;
    }
}

遍历

class Solution {
    public int numWays(int n) {
        // 定义 n = 0 与 n = 1 的结果
        int a = 1, b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}