與貪心算法求局部最優(yōu)解相比哥桥，動態(tài)規(guī)劃求的是全局最優(yōu)解（但不是每個問題都有最優(yōu)解笋妥，比如NP完全問題就沒有最優(yōu)解）
例：背包問題之動態(tài)規(guī)劃解決
問題描述：
現(xiàn)在有一個背包可以裝4磅物品柳洋，現(xiàn)在要從商城里拿盡可能價值高的物品裝進包里锁蠕。
商城物品情況如下
| 商品名 | 吉他 | 筆記本 | 音箱 |
|---|---|---|---|
| 價值 | 1500 | 2000 | 3000 |
| 重量 | 1 | 3 | 4 |
每個動態(tài)規(guī)劃都從一個網(wǎng)格（如下）開始
現(xiàn)在一行一行地填充該網(wǎng)格。
| 物品\物品重量 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 吉他 | ||||
| 音箱 | ||||
| 筆記本 |
每個格子的計算公式：
填充吉他行 目前最大價值1500（吉他）
| 物品\物品重量 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 吉他 | 1500 | 1500 | 1500 | 1500 |
| 音箱 | ||||
| 筆記本 |
填充音箱：目前最大價值3000（音箱）
| 物品\物品重量 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 吉他 | 1500 | 1500 | 1500 | 1500 |
| 音箱 | 1500 | 1500 | 1500 | 3000 |
| 筆記本 |
填充筆記本：目前最大價值3500（吉他+筆記本）
| 物品\物品重量 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 吉他 | 1500 | 1500 | 1500 | 1500 |
| 音箱 | 1500 | 1500 | 1500 | 3000 |
| 筆記本 | 1500 | 1500 | 2000 | 3500 |
動態(tài)規(guī)劃的原則就是將大問題拆解成多個小問題征堪，先把小問題的最優(yōu)解求出，再在考慮小問題最優(yōu)解的前提下背桐，得出最終問題的最優(yōu)解
本例的背包問題中优烧，先求出只有吉他一種物品時的最優(yōu)解，再逐步添加物品链峭，最終求出最優(yōu)解
關于網(wǎng)格計算公式的補充：
整個動態(tài)規(guī)劃求解過程中畦娄，是從小問題層逐步求解到大問題，自然每個格子要考慮的第一點就是前一格子的最大值弊仪，又熙卡，新的一層添加了新物品，所有也要考慮新物品的價值+剩余可用磅數(shù)的最大價值（上一層求得）
背包問題補充：
若再添加一個物品——項鏈{‘價值’：1000$励饵，‘重量’：0.5磅}
此時如果沿用之前的網(wǎng)格
則會出現(xiàn)考慮不周的情況（0.5磅重量無法考察）
因此驳癌，當新加入的物品重量小于當前物品重量最小劃分時，需要重新劃分網(wǎng)格役听。
劃分規(guī)則：最大重量//最小重量 即為區(qū)間數(shù)颓鲜。
加入0.5磅的項鏈之后，新的網(wǎng)格為：
| 物品\物品重量 | 0.5 | 1 | 1.5 | 2 | 2.5 | 3 | 3.5 | 4 |
|---|---|---|---|---|---|---|---|---|
| 吉他 | ||||||||
| 音箱 | ||||||||
| 筆記本 | ||||||||
| 項鏈 |
如果要裝的物品為燕麥典予，木豆甜滨，大米這種可以一部分一部分取出的物品
動態(tài)規(guī)劃則解決不了這種情形，貪心可以瘤袖。
旅游行程問題
| 景點名（倫敦） | 威斯敏特 | 雙球劇場 | 英國美術館 |
|---|---|---|---|
| 價值 | 7 | 6 | 9 |
| 花費時間 | 0.5 | 0.5 | 1 |
當然我們可以用動態(tài)規(guī)劃的網(wǎng)格法來得到一條最有價值的旅游路線
如果加入以下景點
| 景點名（巴黎） | 埃菲爾鐵塔 | 盧浮宮 | 巴黎圣母院 |
|---|---|---|---|
| 價值 | 8 | 9 | 7 |
| 花費時間 | 1.5 | 1.5 | 1.5 |
在去巴黎的景點所花費的時間中衣摩，有0.5天是從倫敦前往巴黎的時間。
因此如果先去了埃菲爾鐵塔,則去巴黎的剩下兩個景點的花費時間也要減少2個小時
這種情況就不能使用之前的動態(tài)規(guī)劃算法孽椰。
動態(tài)算法處理的每個子問題都是離散的
再來看一個案例
假如你要經(jīng)營一個網(wǎng)站昭娩，網(wǎng)站主要任務是：英文單詞翻譯。即用戶輸入英文單詞黍匾，你給出相應的翻譯。 例用戶輸入fish呛梆，網(wǎng)站輸出魚
如果用戶輸入的hish锐涯，但詞典中并沒有該單詞，此時應給出相似詞填物。
怎么樣才算是相似詞呢纹腌？判斷最大子串長度？
利用動態(tài)規(guī)劃求出兩字符串（fish和hish）的最大字串長度
動態(tài)規(guī)劃解決問題總是要先知道網(wǎng)格中的各個元素：
兩個坐標軸是什么滞磺？網(wǎng)格中的值是什么（通常為要優(yōu)化的指標）
1升薯，分解問題：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）击困∠雅考慮兩個坐標軸為兩個單詞广凸，則網(wǎng)格中的值為最大子串的長度。
| f | i | s | h |
|---|---|---|---|
| h | |||
| i | |||
| s | |||
| h |
接下來填充該網(wǎng)格蛛枚。不斷驗證得到單元格公式：
單元格公式解釋：
1）兩字母相同谅海，則局部最大字串要延長，即斜上方（cell[i][j]）的值加一(這里指標值在斜方向上累加)
2）若是不同蹦浦，則局部最大字串為0
| * | h | i | s | h |
|---|---|---|---|---|
| f | 0 | 0 | 0 | 0 |
| i | 0 | 1 | 0 | 0 |
| s | 0 | 0 | 2 | 0 |
| h | 0 | 0 | 0 | 3 |
兩字符串的最大字串長度即為網(wǎng)格中的最大值3扭吁。
如果用戶輸入fosh，那么要返回fish還是fort呢盲镶？
如果判斷依據(jù)為最大子串侥袜，則會返回fort，但實際上fish和fosh更像溉贿！
因此我們考慮判斷依據(jù)為兩字符串的最大公共子序列長度（即兩字符串公共字符的個數(shù)）
求最大公共子序列的單元格公式為：
| * | f | o | s | h |
|---|---|---|---|---|
| f | 1 | 0 | 0 | 0 |
| o | 1 | 2 | 2 | 2 |
| r | 1 | 2 | 2 | 2 |
| t | 1 | 2 | 2 | 2 |
fosh和fort的最大公共子序列長度為2
| * | f | o | s | h |
|---|---|---|---|---|
| f | 1 | 0 | 0 | 0 |
| i | 1 | 1 | 1 | 1 |
| s | 1 | 1 | 2 | 2 |
| h | 1 | 1 | 2 | 3 |
fosh和fish的最大公共子序列長度為3
此時就可以返回正確結果fish而非fort系馆。
小結
1，動態(tài)規(guī)劃通常用于解決在給定約束條件下優(yōu)化某個指標值
2顽照，動態(tài)規(guī)劃的原則就是：將大問題分解成小問題由蘑，在解決了小問題的條件下，逐步求解大問題代兵。（一個分解問題的方法就是尼酿，將條件逐漸減少，從最簡單的情況開始分析）
3植影，動態(tài)規(guī)劃使用的一個必要條件為：分解出來的每個小問題都是離散的
4裳擎，每種動態(tài)規(guī)劃方案都設計網(wǎng)格
4.1，網(wǎng)格的每個格子都是一個小問題
4.2思币，網(wǎng)格的每個格子的值都是指標的值
4.3鹿响，單元格計算公式需要具體問題具體分析。
