以前看到这道题感觉都不会(没看过题解)，现在遇到直接就会解了，看来写写题目还是有用的: )

思路

1. 正向的想法是根据只有1个台阶/2个台阶/3个台阶来递推...但是这样会很麻烦
2. 逆向的思维是考虑如果现在已经是n阶台阶了，那么上一步只有两种可能，n-1阶或者n-2阶（因为青蛙只能跳1阶或者2阶），因此把这两种可能性相加就会得到n阶的组合可能性，推导得到公式 F(n) = F(n-1)+F(n-2),即斐波那契数列公式，不过这里的f(0) = 1 , f(1) = 1, f(2) = 2
3. 同理这里也会有矩阵快速幂的解法

class Solution {
    public int numWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int q,p,r,index;
        q = 1; // 1阶 1种
        p = 2; // 2阶 2种
        r = 0;
        index = 3;
        while (index <= n) {
            r = (q+p)%1000000007;
            q = p;
            p = r;
            index ++;
        }
        return r;
    }
}

Q.E.D.