剑指offer 10-2 青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

很容易想到递归的做法, 比如: 100台阶的可能方法 = 99台阶的方法 + 98台阶的方法, 但是很容易时间爆表.

反过来想, 3台阶的方法 = 1台阶方法 + 2台阶方法. 于是我们可以用类似斐波那契数列的方法构造数组, 来获得第100个位置的结果

同样的, 结果容易溢出int类型, (为什么是1e9+7? 两个1e9+7无限接近与int极限!->两个int相加之后再取mod), 每次相加得到的结果取一次余数

int numWays(int n){
    if(n == 0) return 1;
    int result[101];
    for(int i = 1; i<=n ; i++)
    {
        if(i == 1) result[i] = 1;
        else if(i == 2) result[i] = 2;
        else
        {
            result[i] = (result[i-1] + result[i-2] )%(int)(1e9+7);
        }
    }

    return result[n];

}