70. Climbing Stairs

思路：递归 --> memo --> DP

斐波那契数列:

• 公式：

public int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 0; i < n; i++) {
        a = (b = b + a) - a;
    }
    return a;
}

• Recursion && memorization:

def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    memo = [-1 for i in range(n + 1)]
    def cb(n):
        if n == 0 or n == 1:
            return 1
        if memo[n] == -1:
            memo[n] = cb(n - 1) + cb(n - 2)
        return memo[n]
    return cb(n)

• DP：

递推式:f(n) = f(n - 1) + f(n - 2)的意思举例来说，当n = 4时，f(4) = f(3) + f(2)代表从三级台阶可以跳一级到达四级，也可以从二级台阶跳两级跳到四级，所以结果为两数之和。注意java中n过大结果会溢出。

public int climbStairs(int n) {
    int[] memo = new int[n + 1];
    memo[0] = memo[1] = 1;
    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

变态跳台阶

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

和之前普通跳台阶的递推式差不多，比如

f(4) = f(3) + f(2) + f(1) // 四级台阶可以由三级，二级，一级台阶跳上来
f(3) = f(2) + f(1)        // 三级可以由二级，一级台阶跳上来
--------------------------
f(4) = 2 * f(3)

由等比数列递推式推出f(n) = 2 ^ (n - 1) * f(1)
又因为f(1) = 1

所以f(n) = 2 ^ (n - 1)

public int climbStairsII(int target) {
    return 1 << target - 1;
}

矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

n
0 ---> 0
1 ---> 1
2 ---> 2
3 ---> 3
4 ---> 5

public int RectCover(int target) {
    if (target == 0) return 0;
    int a = 1, b = 1;
    while (target-- > 0) {
        a = (b += a) - a;
    }
    return a;
}