10-2 变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

变态跳台阶问题，是斐波那契额数列 青蛙跳台阶 跳楼梯问题的变形。

假设当前在3台阶，那么可能从0级跳到3台阶 1台阶到3台阶 2台阶到3台阶 3台阶到3台阶。

f(3) = f(1)+f(2)+f(3)

f(1) = 1

f(2) = 2

f(3) = 1+2+1

1.暴力解

public int JumpFloorII(int target) { if(target == 0 || target == 1) { return 1; } int [] f = new int [target+1]; f[0] = f[1] = 1; for(int i=2;i<=target;i++){ for(int j=0;j<i;j++){ f[i] += f[j]; } } return f[target]; }

2.递归

f(n) = 2^(n-1) 找到规律

public int JumpFloorII(int target) { if(target < 0){ return -1; }else if(target == 1){ return 1; }else{ return 2*JumpFloorII(target-1); } }