前言
需要在給定限制條件下優化某種名額時，動态規劃很有用。
問題可分解為離散子問題時，可使用動态規劃來解決。
每種動态規劃解決方案都涉及網格。
單元格中的值通常就是你要優化的值。
每個單元格都是一個子問題，是以你需要考慮如何将問題分解為子問題。
背包問題
小偷背着一個可裝4磅東西的背包，可盜竊的商品有如下3件。為了讓盜竊的商品價值最高，該選擇哪些商品？
近似解方法找到的可能不是最優解。那麼如何找到最優解呢？
每個動态規劃算法都從一個網格開始，背包問題的網格如下。
第一行是吉他行，意味着你将嘗試将吉他裝入背包。在每個單元格，都需要做一個簡單的決定：偷不偷吉他？目标是找出一個價值最高的商品集合。
填充下一行——音響行。可偷的商品有吉他和音響。在每一行，可偷的商品都為目前行的商品以及之前各行的商品。
逐漸更新最大價值
以同樣的方式處理筆記本電腦
對于容量為4磅的背包，情況很有趣。這是非常重要的部分。目前的最大價值為3000美元，你可不偷音響，而偷筆記本電腦，但它隻值2000美元。
價值沒有原來高。但等一等，筆記本電腦的重量隻有3磅，背包還有1磅的容量沒用！
在1磅的容量中，可裝入的商品的最大價值是多少呢？你之前計算過。
根據之前計算的最大價值可知，在1磅的容量中可裝入吉他，價值1500美元。是以，你需要做如下比較。
筆記本電腦和吉他的總價值為3500美元，是以偷它們是更好的選擇。最終的網格類似于下面這樣。
計算每個單元格的價值時，使用的公式都相同。這個公式如下：
各行的排列順序無關緊要。
增加一件更小的商品時，需要考慮的粒度更細，是以必須調整網格。
不考慮偷商品的一部分
使用動态規劃時，要麼考慮拿走整件商品，要麼考慮不拿，而沒法判斷該不該拿走商品的一部分。
但使用貪婪算法可輕松地處理這種情況！首先，盡可能多地拿價值最高的商品；如果拿光了，再盡可能多地拿價值次高的商品，以此類推。
旅遊行程最優化
對于想去遊覽的每個名勝，都列出所需的時間以及你有多想去看看。根據這個清單，确定兩天時間該去遊覽哪些名勝。
網格類似于下面這樣。
假設你還想去巴黎，是以在前述清單中又添加了幾項。
從倫敦前往巴黎，這需要半天時間。不是去每個地方都得先從倫敦到巴黎。将埃菲爾鐵塔加入“背包”後，盧浮宮将更“便宜”：隻要1天時間，而不是1.5天。
動态規劃能夠解決子問題并使用這些答案來解決大問題。但僅當每個子問題都是離散的，即不依賴于其他子問題時，動态規劃才管用。這意味着使用動态規劃算法解決不了去巴黎玩的問題。
最長公共子串
使用者在網站輸入單詞時，需要給出其定義。但如果使用者拼錯了，必須猜測他原本要輸入的是什麼單詞。例如，Alex想查單詞fish，但不小心輸入了hish。但網站的字典中，根本就沒有這樣的單詞，但有幾個類似的單詞。你需要判斷是哪個。
在這個例子中，你要找出兩個單詞的最長公共子串。
用于解決這個問題的網格是什麼樣的呢？要确定這一點，你得回答如下問題。
單元格中的值是什麼？
如何将這個問題劃分為子問題？
網格的坐标軸是什麼？
單元格中的值通常就是你要優化的值。在這個例子中，這很可能是一個數字：兩個字元串都包含的最長子串的長度。
如何将這個問題劃分為子問題呢？你可能需要比較子串：不是比較hish和fish，而是先比較his和fis。每個單元格都将包含這兩個子串的最長公共子串的長度。這也給你提供了線索，讓你覺得坐标軸很可能是這兩個單詞。是以，網格可能類似于下面這樣。
最終的網格如下：
僞代碼如下：
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = 0
查找單詞hish和vista的最長公共子串時，網格如下。
但對于最長公共子串問題，答案為網格中最大的數字——它可能并不位于最後的單元格中。
最長公共子序列
假設Alex不小心輸入了fosh，他原本想輸入的是fish還是fort呢？
我們使用最長公共子串公式來比較它們。
最長公共子串的長度相同，都包含兩個字母！但fosh與fish更像。
這裡比較的是最長公共子串，但其實應比較最長公共子序列：兩個單詞中都有的序列包含的字母數。
下面是填寫各個單元格時使用的公式。
僞代碼如下：
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
動态規劃都有哪些實際應用呢？
生物學家根據最長公共序列來确定DNA鍊的相似性，進而判斷度兩種動物或疾病有多相似。最長公共序列還被用來尋找多發性硬化症治療方案。
你使用過諸如git diff等指令嗎？它們指出兩個檔案的差異，也是使用動态規劃實作的。
前面讨論了字元串的相似程度。編輯距離（levenshtein distance）指出了兩個字元串的相似程度，也是使用動态規劃計算得到的。編輯距離算法的用途很多，從拼寫檢查到判斷使用者上傳的資料是否是盜版，都在其中。
你使用過諸如Microsoft Word等具有斷字功能的應用程式嗎？它們如何确定在什麼地方斷字以確定行長一緻呢？使用動态規劃！