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

一.题目描述
JZ9 跳台阶扩展问题
题目链接:https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
注意审题:该题青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级.
二.算法1(找规律)

可发现 1，2，4，8，16，32（n=1,2,3,4,5,6）即2^(n-1).找到规律可以求出n阶台阶的方案数了.

class Solution {
public:
    int jumpFloorII(int number) {
        long long a=2,b=number-1,c=1;
        while(b){//用的快速幂求2^(n-1)速度更加快
            if(b%2) c*=a;
            a*=a;
            b/=2;
        }
        return c;
    }
};

复杂度:o(logn)
优缺点:实现比较方便,但是规律不容易发现要至少例举到5才可以发现规律
三.算法2(递归)


两式相减得:
得到上述关系式子直接上代码:

class Solution {
public:
    int jumpFloorII(int number) {
        if(number<= 0)
            return -1;
        else if(number==1)
            return 1;
        else{
            return 2*jumpFloorII(number-1);
        }
    }
};

复杂度:o(n)
优缺点:实现比较简单,但是利用函数进行推导不容易想到.