1. Python之動態規劃演算法
動態規劃演算法中是將復雜問題遞歸分解為子問題，通過解決這些子問題來解決復雜問題。與遞歸演算法相比，動態編程減少了堆棧的使用，避免了重復的計算，效率得到顯著提升。
先來看一個簡單的例子，斐波那契數列.
斐波那契數列的定義如下。
斐波那契數列可以很容易地用遞歸演算法實現：
上述代碼，隨著n的增加，計算量呈指數級增長，演算法的時間復雜度是 。
採用動態規劃演算法，通過自下而上的計算數列的值，可以使演算法復雜度減小到 ，代碼如下。
下面我們再看一個復雜一些的例子。
這是小學奧數常見的硬幣問題： 已知有1分，2分，5分三種硬幣數量不限，用這些硬幣湊成為n分錢，那麼一共有多少種組合方法。
我們將硬幣的種類用列表 coins 定義；
將問題定義為一個二維數組 dp，dp[amt][j] 是使用 coins 中前 j+1 種硬幣( coins[0:j+1] )湊成總價amt的組合數。
例如： coins = [1,2,5]
dp[5][1] 就是使用前兩種硬幣 [1,2] 湊成總和為5的組合數。
對於所有的 dp[0][j] 來說，湊成總價為0的情況只有一種，就是所有的硬幣數量都為0。所以對於在有效范圍內任意的j，都有 dp[0][j] 為1。
對於 dp[amt][j] 的計算，也就是使用 coins[0:j+1] 硬幣總價amt的組合數，包含兩種情況計算：
1.當使用第j個硬幣時，有 dp[amt-coins[j]][j] 種情況，即amt減去第j個硬幣幣值，使用前j+1種硬幣的組合數；
2.當不使用第j個硬幣時，有 dp[amt][j-1] 種情況，即使用前j種硬幣湊成amt的組合數；
所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]
我們最終得到的結果是：dp[amount][-1]
上述分析省略了一些邊界情況。
有了上述的分析，代碼實現就比較簡單了。
動態規劃演算法代碼簡潔，執行效率高。但是與遞歸演算法相比，需要仔細考慮如何分解問題，動態規劃代碼與遞歸調用相比，較難理解。
我把遞歸演算法實現的代碼也附在下面。有興趣的朋友可以比較一下兩種演算法的時間復雜度有多大差別。
上述代碼在Python 3.7運行通過。