一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloorII(int target) {
return 1<<(target-1);
}
}
可以求出通项公式：2^(target-1)
- 方法1：
target = 1； return 1；
target = 2；return 2；
target = 3； 如果跳上第一级台阶，剩下还有两级台阶 target = 2 种跳法；如果不跳上第一级台阶，需要从地上跳第二三级台阶，还是 target = 2 种跳法； return 2*（target=2）；
target = 4； 如果跳上第一级台阶，剩下还有三级台阶 target = 3 种跳法；如果不跳上第一级台阶，需要从地上跳第二三四级台阶，还是 target = 4 种跳法； return 2*（target=3）；··· - 方法2：
对于1~target-1级台阶，可跳可不跳，target台阶必须跳，所以2^(target-1)种情况。 - 方法3：
target = 0； return 1；
target = 1； return 1；
target = 2； return 从0-2一步和从1-2一步；2
target = 3； return 从0-3一步，从1-3一步，从2-3一步；4
target = 4；1 1 2 4 = 8；
target = 5；1 1 2 4 8 = 16；···
