剑指offer第9题：变态跳台阶

题目描述

变态跳台阶

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

分析

类似于,要想跳到n阶，此时有n中情况：
1.从0阶，跳上n阶到n阶，
2.从1阶，跳上n-1阶到n阶
3.从2阶，跳上n-2阶到n阶
以此类推
。。。
n.从n-1阶，跳上1阶到n阶。

总结上述分析：
递归的思路：
假设跳上n阶一共有F(n)种方法，那么F(n) = 1+F(1)+F(2)+…+F(n-1).若用递归，为了分析时间复杂度不妨取n=4，计算F(1),1次，计算F(2),需计算F(1).2次，计算F(3),则需要计算F(2),F(1),需要大量重复计算，时间复杂度在O(n^n)!!!相当可怕。但是貌似牛客网给的测试例程比较小，竟然通过了！
非递归的思路
有上面的分析可知：F(n) = 1+F(1)+F(2)+…+F(n-1).那么F(n-1) = 1+F(1)+F(2)+…F(n-2)，看到这你想到了啥，哈哈，当然直接将后式带到前式右边，惊奇地发现F(n) = F(n-1) +F(n-1) = 2*f(n-1).而且F(1) = 1,这样子就知道数列的前几项为：0,1,2,4,…那F(n) = 2^(n-1)。F(0) = 0。是不是很简单，由于要循环算n次乘法，所以时间复杂度为o(n);利用左移操作符“<<”可以快速计算乘二的乘法。

源码

递归

class Solution {
public:
    int jumpFloorII(int number) {
	    if(number == 0) return 0;
	    if(number == 1) return 1;
	    if(number > 1)
	    {
	        int sum = 1;
	        for(int i = 0;i<number;i++)
	        {
	            sum += jumpFloorII(i);
	        }
	     return sum;
	    }
    }
};

非递归

利用标准库函数pow(x,y)。

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 0) return 0;
        else return pow(2,number-1);//标准库函数pow(x,y)，返回值是x^y。
    }
};

利用左移运算符

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