题解 | #跳台阶扩展问题#

题目难度：简单
题目考察：dp，记忆化搜索，递推
题目内容：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
首先有一题限制了一次可以跳一步或者两步传送门
在那一题状态转移方程为f[i]=f[i-1]+f[i-2]
这一题是可以跳任意步，很容易类比出来f[i]=f[0]+f[1]+f[2]+...+f[i-1],f[0]表示从起点一次跳n步，f[1]表示从第一格一次跳n-1格，以此类推
既然有了递推表达式，所以一定可以用递归来求解
算法1（递归）

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0)return 1;//终止条件
        int ans=0;
        for(int i=0;i<number;i++)
            ans+=jumpFloorII(i);//f[i]=f[0]+f[1]+f[2]+...+f[i-1]
        return ans;
    }
};

复杂度分析：时间复杂度，每次调用f[n-1],f[n-2],f[n-3]所以时间复杂度为O(n^n)
空间复杂度，没有额外空间，空间复杂度O(1)
可以发现，时间复杂度非常高，同理，可以用记忆化搜索进行优化
算法2（记忆化搜索）

class Solution {
public:
    int f[1001]={0};
            //记录f[n]有没有被搜索过
    int jumpFloorII(int number) {
        if(f[number])return f[number];
            //如果f[n]被搜索过直接返回f[n]
        if(number==0)return 1;//终止条件
        for(int i=0;i<number;i++)
            f[number]+=jumpFloorII(i);
            //f[i]=f[0]+f[1]+f[2]+...+f[i-1]
        return f[number];//返回f[n]
    }
};

复杂度分析：时间复杂度，每个f[i]只会被搜到一次所以时间复杂度为O(n)
空间复杂度，定义了额外空间保存f[n]的值，空间复杂度O(n)
算法3（递推）
观察状态转移方程f[i]=f[0]+f[1]+f[2]+...+f[i-1]
f[i+1]=f[0]+f[1]+f[2]+...+f[i-1]+f[i]=2f[i]
这时即f[i]=2f[i-1]=2^(n-1)
这时问题就转化为了给一个n求出2^(n-1)
可以采用快速幂优化到O(logn)空间复杂度优化到O(1)
代码如下

class Solution {
public:
    int jumpFloorII(int number) {
        number--;
        int ans=1,a=2;
        while(number)
        {
            if(number&1)ans=ans*a;
            a=a*a;
            number>>=1;
        }
        return ans;
    }
};

时间复杂度O(logn)
空间复杂度O(1)
思考
递推的过程发现了这个问题转化为了2^n-1,但是需要推导，递归方法求dp显得十分清晰，不用推导，加上记忆化搜索使得时间复杂度和空间复杂度都在一个客观的范围内