本章内容
學習動态規劃,這是一種解決辣手問題的方法,将問題分解成小問題
學習如何設計問題的動态規劃解決方案
背包問題
每個動态規劃問題都從網格開始
再加入一個物品如何比如iPhone 2000元 1磅
增加一件更小的商品呢?0.5磅,1000元
當且僅當每個字問題是離散的,即不依賴其他子問題時,動态規劃才管用。
最優解可能大緻包不滿。
動态規劃問題的感想
- 動态規劃問題幫助你在給定限制條件下找到最優解,隻有當問題是離散的才有效果
- 每種動态規劃問題都涉及網格
- 每個單元格都是一個子問題
繪制網格
繪圖前确定
- 單元格的值是什麼
- 如何劃分為子問題
- 網格坐标軸是什麼
費曼算法
- 将問題寫下來
- 好好思考
- 将答案寫下來