問題：10階層樓梯，每次只能走一階或兩階，問有多少種走法？

遞歸法

設F(n)是爬到n階層的走法數(shù)，那么
F(10) = F(9) + F(8)
F(9) = F(8) + F(7)
...
F(3) = F(2) + F(1)
F(1) 為1中走法，F(xiàn)(2)為2種走法，故編程如下

int getClimbWays(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return getClimbWays(n - 1) + getClimbWays(n - 2);
}

計算結果是89種，通過該方法就可以計算任意階層的走法。
復雜度分析：
時間復雜度：O(2ⁿ)，因為每次調(diào)用都會執(zhí)行該方法兩次。這個復雜度隨著n的增大，執(zhí)行時間會急劇增加，故需要優(yōu)化。

這個方法的遞歸圖如下

可以看到有很多重復的遞歸調(diào)用,我們可將已經(jīng)計算的結果通過Hash表保存起來，如果需要時取出即可，這就稱為備忘錄算法

備忘錄算法

class Solution {
    // 利用Hash表存儲
    HashMap<Integer, Integer> map = new HashMap<>();
    int getClimbWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int value = getClimbWays(n - 1) + getClimbWays(n - 2);
        map.put(n, value);
        return value;
    }
}

復雜度分析：
時間復雜度：O(n),需要方法調(diào)用的只有F(1)->F(n)各一次
空間復雜度：O(n),HashMap種會存儲n-2個數(shù)據(jù)，對于F(1)和F(2)不會存儲

由于引入了HaspMap導致空間復雜度增大。我們是否可以繼續(xù)優(yōu)化？原問題可以拆分為小問題，然后求解，F(1) = 1,F(2) = 2,F(3) = F(1) + F(2) ... F(n) = F(n-2) + F(n-1),我們可以從最小問題入手，發(fā)現(xiàn)后面解時前面兩個解的和，我們就可以采用迭代的方式的完成。這就是動態(tài)規(guī)劃

動態(tài)規(guī)劃

class Solution {
    int getClimbWays(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a = 1;
        int b = 2;
        for (int i = 2; i < n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)