题目描述

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

分析：
DP(n)代表跳上第n级台阶的次数。
DP(0) = 1
DP(1) = DP(1 - 1)
DP(2) = DP(2 - 1) + DP(2 - 2)
DP(3) = DP(3 - 1) + DP(3 - 2) + DP(3 - 3) // 3 - 1代表最后一次跳了1级台阶，3 - 2代表最后一次跳了2级台阶......
......
DP(n) = DP(n-1) + DP(n - 2) + DP(n - n)
DP(n-1) = DP(n - 2) + DP(n - 3) + DP(n - n)
上面两式相减，得：
DP(n) = 2 * DP(n - 1) 
public class Solution {
    public int JumpFloorII(int target) {
        if (target == 1){
            return target;
        }
        int f1 = 1;
        int f2 = 2 * f1;
        for(int i = 3; i <= target; i++) {
            f2 += 2 * f1;
            f1 = f2 / 2;
        }
        return f2;
    }
}