题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解体思路1
对于本题,假设总跳法数量为f(n)，通过分析可以知道： f(n) = f(n-1) + f(n-2) + … +f(1) + 1 代码实现1(两层迭代):
public class Solution {
public int JumpFloorII(int target) {
if( target <= 2)
return target;
int[] fn = new int[target];
fn[0] = 1;
fn[1] = 2;
for(int i=2; i<target; i++) {
for(int j=0; j<i; j++) {
fn[i] += fn[j];
}
fn[i]++;
}
return fn[target - 1];
}
}
解体思路2
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+…+f(1) 因为f(n-1)=f(n-2)+f(n-3)+…+f(1) 所以f(n)=2*f(n-1)
代码实现1(递归）：
public class Solution {
public int JumpFloorII(int target) {
if(target <= 2) {
return target;
} else {
return 2 * JumpFloorII(target - 1);
}
}
}
代码实现2：（位运算,速度更快）
public class Solution {
public int JumpFloorII(int target) {
int fn1 = 1;
return fn1 << (target - 1);
}
}