一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
跳n级台阶=
第一次跳n(1)+
第一次跳n-1,剩下跳1级(1)+
第一次跳n-2,剩下跳2级(2)+
第一次跳n-3,剩下跳3级(4)+
...
第一次跳3,剩下跳n-3级+
第一次跳2,剩下跳n-2级+
第一次跳1,剩下跳n-1级
f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
f(n-1) = f(n-2) + ... + f(1) + f(0)
=> f(n) = 2f(n-1)
Java
public class Solution {
public int JumpFloorII(int target) {
if (target <= 2) {
return target;
}
return JumpFloorII(target-1)*2;
}
}
不使用递归
public class Solution {
public int JumpFloorII(int target) {
if (target <= 2) {
return target;
}
int sum = 2;
for (int i = 3; i <= target; i++) {
sum = 2*sum;
}
return sum;
}
}
网友评论