题解 | #跳台阶扩展问题#
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
如果一次可以跳任意阶，那么要想跳到第n阶，可以从前面任意一阶跳过去，即f(n)=f(n-1)+f(n-2)+……+f(2)+f(1)。
同理，f(n-1)=f(n-2)+f(n-3)+……+f(2)+f(1), 那么f(n) = 2 * f(n-1).
依此类推，f(n-1)=2 * f(n-2), …… f(2) = 2 * f(1), 而f(1) = 1;
故，f(n)=2 ^ (n-1);
int jumpFloorII(int number ) {
if(number < 0)
return -1;
else if(number == 0 || number == 1)
return 1;
else
// return 2 * jumpFloorII((number - 1)); //这是用递归的方法表示，比较慢
return 1<<(number-1); //用移位的方法表示2的幂就快一些
}
