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

思路

分析一下，如果青蛙位于台阶n上，因为青蛙只能跳一阶或2阶，所以只能从n - 1阶或n - 2阶跳过来，所以我们可以得到一个递推公式f(n) = f(n - 1) + f(n - 2)

所以就是和斐波那契的做法是一样的。
参考：斐波那契

class Solution {
    final int mod = 1000000007;
    int[] match = new int[110];
    {
        match[0] = 1; match[1] = 1; match[2] = 2;
    }
    public int numWays(int n) {
        if(n == 0) return 1;
        if(match[n] != 0) return match[n];
        return match[n] = (numWays(n - 1) + numWays(n - 2)) % mod;
    }
}