剑指offer 跳台阶扩展问题

跳台阶扩展问题

题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法？

解题：

f[0]=f[1]=1
f[n]=f[n-1]+f[n-2]+…+f[0]
因为 f[n-1]=f[n-2]+…+f[0]
所以 f[n]=2 * f[n-1]
同理 f[n-1]=2 * f[n-2]
最终得到 f[n]=2 * 2 * 2 * … * f[0]

代码：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==1 || number==0){
            return 1;
        }
        int sum=1;
        //因为0和1都是1所以从哪里开始都无所谓
        for(int i=1;i<number;i++){
        //左移乘2，右移除以2
            sum=sum<<1;
        }
        return sum;
    }
};