讀書筆記 《算法圖解》第九章 動态規劃

背包問題

每次疊代時，你都存儲目前的最大價值。最大價值不可能比一起低！

動态規劃不能隻偷商品的一部分

要麼偷走整個商品

要麼不偷

貪婪算法可以解決這個問題（先大後小）

動态規劃解決不了互相依賴的情況

根據動态規劃算法的設計，最多隻需合并兩個子背包，根本不會涉及兩個以上的子背包，不過這些子背包裡面又包含子背包

動态規劃可幫助你在給定限制條件下找到最優解，在背包問題中，你必須在背包容量給定的情況下，偷到價值最高的商品。

此問題可分解為彼此獨立且離散的子問題時，就可使用動态規劃解決

tips：

• 每種動态規劃解決方案都涉及網絡
• 單元格中的值通常就是你要優化的值。在前面的背包問題中，單元格的值為商品的價值
• 每個單元格就是一個子問題，是以你應考慮如何将問題分成子問題，這有利于找出網絡的坐标軸

動态規劃的實際應用

• 尋找DNA的相似性
• git diff 找到兩個檔案之間的差異
• 編輯距離
• word文檔斷字功能保證行長一緻

沒有放之四海皆準的計算動态規劃解決方案的公式