【剑指Offer】变态跳台阶

问题描述:

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

解题思路:

每一次调用函数都是查找这个楼梯数有多少种跳法,如果楼梯数已为0,
则表明只有这一种跳法,也就是没有下一步的跳法了;
若不为0,则设这一步会跳1、2、3~n阶,然后将跳完这一步的
下一步跳法的跳法相加,返回结果。

示例:
n=4
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4

代码实现

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

在牛客网上看到了一个变态算法,只用了一行代码。。。

return  1<<--number;

这个答案的原因是n级台阶里,除了最后一级台阶必须要跳外,每级台阶都存在跳与不跳两种情况,所以共有2^(n-1)中跳法,上述代码是用移位操作直接算出了答案。