解:把n级台阶时的跳法记为f(n),当n>2时,第一次跳的时候有两种不同的选择:一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另外一种是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2);因此n级台阶时的跳法为f(n)=f(n-1)+f(n-2)。不难看出这实际是斐波拉契数列的变形应用,把斐波拉契数列的每一项向前移动了1位。
class Solution {
public: int jumpFloor(int number) {
if(number <= 0) {
return 0;
}
else if(number == 1 || number == 2) {
return number;
}
else
{
//int re = 0;
return jumpFloor(number – 1) + jumpFloor(number – 2);
}
}
};
或者根据归纳总结的:2^(n-1)
public int JumpFloor2(int target) {
return (int) Math.pow(2,target-1);
}