Day9 剑指offer：青蛙还跳台阶

一只青蛙一次可以跳上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；···