一、什麼是動態規劃？

動態規劃（Dynamic Programming）是一個非常經典的算法，它的核心思想很簡單：

把一個大問題拆解成已知解的子問題。

怎麼說呢？舉一個簡單的例子吧：

斐波那契數列: 1, 1, 2, 3, 5, 7, 12, 19, 31 ...

即：第一個數和第二個數都是1，接下來的每一個數都是前兩個數的和。

也即：

<code>f(1) = f(2) = 1
f(n) = f(n-1) + f(n-2)/<code>

例如：

<code>f(1) = 1

f(2) = 1

f(3) = f(1) + f(2) = 1+ 1 = 2

f(4) = f(3) + f(2) = 2 + 1 = 3

...

f(n) = f(n-1) + f(n-2)/<code>

假設我們想要求f(4)的值，如果我們已經之前已經計算過f(3)和f(2)就可以直接給出f(4) = f(3) + f(2) = 2 + 1 = 3，而不需要從f(1) = f(2) = 1來一步步推算到第四個數了。

有這樣一句話非常生動的說明了動態規劃的核心：

不能記住歷史，就註定會重複歷史。

二、爬樓梯問題

再來看看經典的爬樓梯問題：

<code>有一個樓梯，一共有n個臺階。
每次你可以上一個或者兩個臺階，那麼爬到樓梯頂有多少中不同的爬法呢？

注意：n是一個正整數 


例子一：
輸入：2個臺階
輸出：2種爬法
解釋：兩種爬法分別為：
1. 爬一個臺階 + 爬一個臺階
2. 爬兩個臺階

例子二：
輸入：3個臺階
輸出：3種爬法
解釋：三種爬法分別為：
1. 爬一個臺階 + 爬一個臺階 + 爬一個臺階
2. 爬一個臺階 + 爬兩個臺階
3. 爬兩個臺階 + 爬一個臺階/<code>

大家先思考一下怎麼解決這個問題？

好了，有想法了嗎？如果沒有思路的話，聯想一下一開始說的動態規劃：把一個大問題拆解成已知解的子問題。

這裡要反直覺地假設一下，如果我現在已經站在樓梯頂（第n個臺階），那我是怎麼上來的呢？

由於我只能一次跨一個或者兩個臺階，所以我上一步必然在第n-1個臺階或者第n-2個臺階上，那麼我爬到樓梯頂的爬法就是爬到第n-1個臺階的爬法+爬到第n-2個臺階的爬法之和，也就是：

<code>f(n) = f(n-1) + f(n-2)/<code>

且一階臺階的爬法只有1種，二階臺階的爬法只有2種（1+1或者2），即：

<code>f(1) = 1
f(2) = 2/<code>

用python代碼實現就是：

<code>class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)/<code>

是不是很簡單？！

是的，以上就是爬梯子問題使用了遞歸（Recursion）方法的暴力解法（Brute Force）。在不考慮時間複雜度和空間複雜度的情況下，能夠解決問題。

三、給遞歸加上記憶(Memoization)

上面的那個解法就是最基本的遞歸解法。

<code>遞歸：一個函數在內部調用自身/<code>

基本的遞歸解法確實能夠解決問題，但是遞歸解法的問題也十分明顯：在n數值大的時候，時間複雜度和空間複雜度非常之大（分別為O(2^n)和O(n)），對於較大的n，甚至無法在給定時間內解出。讓我們看看當n等於5時的遞歸調用樹：

<code>f(5)  
  =  f(4) + f(3) 
  = f(3) + f(2) + f(2) + f(1)
  = f(2) + f(1) + f(2) + f(2) + f(2) + f(1)/<code>

f函數的計算次數實在是太多。

那如何改進呢？

其實很簡單，我們都可以看到對於相同的值，並不需要計算多次，比如說上圖中對於f(1) , f(2), f(3)的結果，只需要在第一次計算後保存下來，下一次需要的時候直接查詢就可以大大減少計算量。

用python代碼實現就是：

<code>class Solution:
    res = {}
    
    def climbStairs(self, n: int) -> int:
        if n == 1:
            self.res[1] = 1
            return 1
        elif n == 2:
            self.res[2] = 2
            return 2
        res_val = self.res.get(n) or self.climbStairs(n-1) + self.climbStairs(n-2)
        self.res[n] = res_val
        return res_val/<code>

以上解法的時間複雜度和空間複雜度可以降低到：O(n) 和 O(n)

四、動態規劃

上面的遞歸解法的思路是自頂向下，先算f(5), 再算f(4), f(3), 再算f(2), f(1)。

那我們能不能利用動態規劃的思路，先算小問題，最後算出大問題，自底向上地算出最終解呢？

當然可以：

<code>已知:
f(1) = 1, f(2) = 2
可知:
f(3) = f(2) + f(1) = 2 + 1 = 3
f(4) = f(3) + f(2) = 3 + 2 = 5
.../<code>

用python代碼實現就是：

<code>class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        res_n_1 = 2
        res_n_2 = 1
        res_n = None
        for i in range(n-2):
            res_n = res_n_1 + res_n_2
            res_n_2 = res_n_1
            res_n_1 = res_n
        return res_n/<code>

時間複雜度和空間複雜度分別為：O(n) 和 O(n)

五、後續

到這裡，有沒有覺得動態規劃其實很簡單呢？

只要掌握了正確了學習方法，加上持之以恆的學習訓練，算法並不難~

上面的爬樓梯問題其實還有性能更優化的方案，你能想到嗎？

我是零度橙子，5年以上python經驗，軟件工程師，科技達人，谷歌認證雲計算架構師，AWS認證devops專家，歡迎大家關注我，瞭解有用有趣的科技知識~

閱讀更多 零度橙子 的文章

關鍵字: 算法 那契 數列