变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 时间限制：1秒 空间限制：32768K
思路
发现规律，f(n) = f(n - 1) + f(n - 2) + … + f(1) + 1, 枚举 f(1) = 1. f(2) = 2, f(3) = 4, f(n) = 2^(n - 1)
补充：dangle的答案解析，将以上式子展开可得：
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：f(n) = 2*f(n-1)
代码
function jumpFloorII(number)
{
// write code here
var result = 1;
while(number > 1) {
result = result * 2;
number--;
}
return result;
}
运行时间：18ms
占用内存： 5332k
最佳代码
function jumpFloorII(number)
{
return 1<<(--number);
}
}
运行时间：11ms
占用内存：5436k
位操作
