剑指 Offer 10- I. 斐波那契数列、II. 青蛙跳台阶问题

这两个都是同一种类型的问题：即斐波那契动态规划问题。

一. 对第一题进行分析

　　对于这种问题，我们首先得出动态规划的转移方程为：f[n] = f[n-1] + f[n-2]，其中 f[0] = 0，f[1] = 1。但是如果我们就这样算，肯定会超出时间限制，因此我们可以用一个数组 dp 来记录算出的斐波那契数列。dp[i] = dp[i-1] + dp[i-2]。这样我们可以得出 dp[3]、dp[4]……这样在我们使用他们的时候，就不用重复计算了，最后返回 dp[n] 即可（根据题目要求，dp[0] = 0不计入项数）。

　　但是我们发现，题目中只需要返回第n项斐波那契常数，不需要记录前面的，因此我们可以简化空间复杂度。定义三个数 p,q=0,r=1（q和r 也就是斐波那契数列的第0项和第1项），进行for循环滑动。

class Solution {
    public final int mod = 1000000007;
    public int fib(int n) {
        if(n<2){
            //n<2直接输出
            return n;
        }else{
            int p,q=0,r=1;
            for(int i=2;i<=n;i++){
                //滑动
                p = q;
                q = r;
                r = (p+q)%mod; //避免溢出
            }
            return r;
        }
    }
}

我们还需要注意：不是在for循环结束后 让 r %= mod，而是在for循环里就不断求余（这两者是等价的），因为不这样做的话，可能在for循环里 r就已经溢出了。 

二. 对第二题进行分析

　　第二题表面上看起来和斐波那契数列没有什么关系，但我们通过动态规划可以发现：对于最后一个台阶，要么是倒数第二个台阶跳一步上来的，要么是倒数第三个台阶跳两步上来的，因此得到动态规划的转移方程为 dp[i] = dp[i-1] + dp[i-2]（跳到倒数第二个台阶上的方法 + 跳到倒数第三个台阶上的方法）。

　　这题与斐波那契不同的地方在于，题目规定 dp[0] = 1，dp[1] = 1。根据降低空间复杂度的方法：我们定义 p,q=1,r=1。

class Solution {
    public int mod = 1000000007;
    public int numWays(int n) {
        if(n==0||n==1){
            return 1;
        }
        int p, q=1,r=1;
        for(int i=2;i<=n;i++){
            p = q;
            q = r;
            r = p + q;
            //不这样有可能越界出现负号
            r%=mod;
        }
        return r;
    }
}