剑指offer 编程题（8）：青蛙跳(随意n阶跳)

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+…+f(1)
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)
所以f(n)=2*f(n-1)

（1）假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)；假定第一次跳的是3阶，那么剩下的是n-3个台阶，跳法是f(n-3)……假定第一次跳的是n-1阶，那么剩下的是1个台阶，跳法是f(1)； 假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是1种；
（2）总跳法为: f(n) = 1+f(n-1) + f(n-2)+….+f(1) （第一个1是跳n阶只有一种方法）
（3）根据（2）可以得出有一阶的时候 f(1) = 1 ；有两阶的时候可以有 f(2) = 1+f(1)=2；有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4…依次内推，有n阶时f(n)=2^(n-1)。

【分析】 每个台阶可以看作一块木板，让青蛙跳上去，n个台阶就有n块木板，最后一块木板是青蛙到达的位子， 必须存在，其他 (n-1) 块木板可以任意选择是否存在，则每个木板有存在和不存在两种选择，(n-1) 块木板 就有 [2^(n-1)] 种跳法，可以直接得到结果。

其实我们所要求的序列为：0,1,2,4,8,16,……
所以除了第一位外，其他位的数都是前一位的数去乘以2所得到的积。

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

class Solution {
public:
    int jumpFloorII(int number) {
            return pow(2,number-1);
    }
};

class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};