僅用于記錄學習，歡迎批評指正，大神勿噴
系列文章目錄
《算法圖解》總結第 1 章：二分查找、大O表示法；
《算法圖解》總結第 2 章：數組和連結清單，選擇排序；
《算法圖解》總結第 3 章：while循環、遞歸、棧；
《算法圖解》總結第 4 章：分而治之、快速排序；
《算法圖解》總結第 5 章：散清單；
《算法圖解》總結第 6 章：廣度優先搜尋；
《算法圖解》總結第 7 章：狄克斯特拉算法；
《算法圖解》總結第 8 章：貪婪算法
《算法圖解》總結第 9 章：動态規劃
《算法圖解》總結第 10 章：K最近鄰算法
《算法圖解》總結第 11 章：十種算法簡介
文章目錄
- 系列文章目錄
- 動态規劃
-
- 原理
- 啟示
- 動态規劃設計方案小貼士
- 補充知識
- 應用案例一：最長公共子串(LCS)
- 應用案例二：最長公共子序列
動态規劃
動态規劃是解決棘手問題的一種方法，它将問題分解成小問題，并先着手解決這些小問題。
原理
在本書中，運用動态規劃解決了兩個問題：背包問題和旅遊行程最優化問題，現在就以旅遊行程最優化的問題為例，介紹一下動态規劃的原理。
旅遊行程最優化
案例：假設你要去倫敦度假，假期兩天，但是想遊覽的地方很多，列出以下清單:
根據清單，決定該遊覽哪些名勝。
案例分析：用動态規劃的方法來分析：
行是對名勝的限制，列是對時間的限制。
第一行：名勝隻有威斯敏斯特教堂，遊覽時間需0.5天，即不管時間是0.5天，1天，1.5天還是2天均隻能遊覽威斯敏斯特教堂，總分值為7。
第二行：名勝裡添加了環球劇場，它的遊覽時間也需0.5天，即名勝有威斯敏斯特教堂和環球劇場，當遊覽時間隻有0.5天時，隻能選擇其一去遊覽，因為7>6，是以選擇遊覽威斯敏斯特教堂，總分值為7，當遊覽時間為1天時，兩個名勝遊覽時間加起來剛好是一天，是以都可以去遊覽，總分值為7+6=13，當遊覽時間大于1天時，由于名勝的限制也隻能遊覽這兩個地方，總分值依然為13。
其他三行分析方法雷同。
從整體來看，在沒有S之前遊覽1.5天最優計劃是W+N，總分值為7+9=16分，因為要遊覽兩天還差0.5天，到達S後，剩餘名勝裡遊覽時間是0.5天的名勝是G和S，因為G的評分為6，S的評分為8，6<8,是以剩餘的0.5天選擇去S，即最優的遊覽計劃是W+N+S，這就運用了将大問題轉化為小問題的方法，即動态規劃。
注意事項：
（1）再增加一個新的名勝，最大價值可能發生變化。
（2）沿着一列往下走時，最大價值不可能比以前低，因為每次疊代時，存儲的都是目前的最大價值。
（3）行的排列順序發生變化時最終的答案是沒有變化的，即各行的排列順序無關緊要。
（4）一般都是選擇逐行填充網格，逐列填充網格可能會對問題産生影響，也可能不會産生影響。
（5）再增加一個新的名勝，遊覽時間僅需0.25天，因為比最小的間隔0.5天要小，此時要調整網格的間隔，調整間隔至0.25天。
（6）動态規劃能處理互相依賴的情況嗎？答案是否定的！比如我們遊覽某個名勝需要1天，那我們可不可以隻遊覽0.5天就傳回呢？現實中是可以的，但是在動态規劃中這種情況是不允許的，要麼選擇遊覽就遊覽完，即遊覽1天，要麼不遊覽，沒法處理遊覽一半的情況。僅當每個子問題都是離散的，即不依賴其他子問題時，動态規劃才管用。
（7）計算最終的解時不會涉及兩個以上的子問題，因為根據動态規劃算法的設計，最終隻需合并兩個子問題。
（8）最優解可能導緻背包沒裝滿，意為時間還沒完全到兩天，已經去完了最佳的遊覽地點。
啟示
從動态規劃問題中，我們得到的啟示是：
（1）動态規劃可幫助我們在給定限制條件下找到最優解。在背包問題中，必須在背包容量給定的情況下，偷到價值最高的商品；在旅行最優化問題中，必須在給定時間内，選擇最優的名勝去遊覽；
（2）在問題可分解為彼此獨立且離散的子問題時，就可使用動态規劃來解決。
動态規劃設計方案小貼士
（1）每種動态規劃解決方案都涉及網格；
（2）單元格中的值通常就是要優化的值；
（3）每個單元格都是一個子問題，是以我們應考慮如何将問題分成子問題，有助于找出網格的坐标軸。
補充知識
子串：原始字元串的一個連續子集
子序列：原始字元串的一個子集
range（）函數使用舉例：
輸出結果：
應用案例一：最長公共子串(LCS)
案例：使用者在某網站輸入單詞時我們需給出定義，若使用者拼錯了，我們必須猜測他原本輸入的是什麼單詞。假設Alex輸入了hish，那他原本要輸入的是fish還是vista呢？
案例分析：
LCS問題解法就是用一個矩陣來記錄兩個字元串中所有位置的兩個字元之間的比對情況，若是比對則為1,否則為0。然後求出對角線最長的1的序列和，其對應的位置就是最長比對子串的位置。以此例示範如下：
算法實作:
def find_lcsubstr(s1, s2):
# 生成0矩陣，為友善後續計算，比字元串長度多了一行一列，原因：
# 當i恰好為最後一個字元時，如果不多加一行一列，i+1和j+1均超出限制，導緻無法繼續計算
m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
#最長比對的長度
mmax=0
#最長比對對應在s1中的最後一位
p=0
# 開始比對
for i in range(len(s1)):
for j in range(len(s2)):
# 如果兩個字母相同，就将目前單元格的值設定為左上方單元格的值加1
#若兩個字母不同，目前單元格的值為0，與假設的相同，此處省略
if s1[i]==s2[j]:
# m是矩陣，其中m[i][j]指的是m矩陣的第i行第i列個元素
m[i+1][j+1]=m[i][j]+1
# 在兩個字母相同的情況下更新最長比對長度
if m[i+1][j+1]>mmax:
mmax=m[i+1][j+1]
# 之是以要令p=i+1是因為輸出字元串s1[p-mmax:p]的時候輸出的是p-mmax至p的前一位。
p=i+1
#傳回最長子串及其長度
return s1[p-mmax:p],mmax
測試1：
輸出結果：
示範算法執行過程：
測試2：
輸出結果：
總結：因為3>2，是以使用者原本要輸入最可能是fish。
應用案例二：最長公共子序列
案例：假設Alex不小心輸入了fosh，那他原本想輸入的是fish還是fort呢？
案例分析：
遇到此類型題時，我們想到了剛才學到的最長公共子串的問題，首先我們先試一下，看一下結果：
print(find_lcsubstr('fosh','fish'))
print(find_lcsubstr('fosh','fort'))
輸出結果：
('sh', 2)
('fo', 2)
因為這兩組例子的最長公共子串的長度均為2，無法用其判斷fosh和fish還是fort更像一些，那麼是否還有其他方法解決此問題呢？我們想到了最長公共子序列算法。
子串要求字元必須是連續的，但是子序列就不是這樣。最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，進而能夠用來辨識抄襲。對一段文字進行修改之後，計算改動前後文字的最長公共子序列，将除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準确。
解法就是用動态回歸的思想，一個矩陣記錄兩個字元串中比對情況，若是比對則為左上方的值加1，否則為左方和上方的最大值。一個矩陣記錄轉移方向，然後根據轉移方向，回溯找到最長子序列。
以此題為例，介紹一下最長公共子序列算法填充網格的過程：
算法實作：
import numpy
def find_lcseque(s1, s2):
# 生成字元串長度加1的0矩陣，m用來儲存對應位置比對的結果
m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
# d用來記錄轉移方向
d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
# 開始比對
for p1 in range(len(s1)):
for p2 in range(len(s2)):
# 如果兩個字母相同，則該位置的值為左上方的值加1
if s1[p1] == s2[p2]:
m[p1+1][p2+1] = m[p1][p2]+1
d[p1+1][p2+1] = 'ok'
# 左值大于上值，則該位置的值為左值，并标記回溯時的方向為left
elif m[p1+1][p2] > m[p1][p2+1]:
m[p1+1][p2+1] = m[p1+1][p2]
d[p1+1][p2+1] = 'left'
# 上值大于左值，則該位置的值為上值，并标記方向up
else:
m[p1+1][p2+1] = m[p1][p2+1]
d[p1+1][p2+1] = 'up'
print numpy.array(d)
# 定義p1和p2的大小
(p1, p2) = (len(s1), len(s2))
s = []
# 注意是從p1和p2的最大值開始循環，轉移方向為None時停止循環
while m[p1][p2]:
c = d[p1][p2]
# 比對成功，插入該字元，并向左上角找下一個
if c == 'ok':
s.append(s1[p1-1])
p1-=1
p2-=1
# 根據标記，向左找下一個
if c =='left':
p2 -= 1
# 根據标記，向上找下一個
if c == 'up':
p1 -= 1
# 回溯，翻轉s
s.reverse()
# 輸出s的長度
print(len(s))
# ＂＂.join() 代表将括号裡面的元素拼接成一個新的字元串
return ''.join(s)
測試：
print(find_lcseque('fosh','fish'))
print(find_lcseque('fosh','fort'))
輸出結果：
[[None None None None None]
[None 'ok' 'left' 'left' 'left']
[None 'up' 'up' 'up' 'up']
[None 'up' 'up' 'ok' 'left']
[None 'up' 'up' 'up' 'ok']]
3
fsh
[[None None None None None]
[None 'ok' 'left' 'left' 'left']
[None 'up' 'ok' 'left' 'left']
[None 'up' 'up' 'up' 'up']
[None 'up' 'up' 'up' 'up']]
2
fo
總結：通過最長公共子序列可以看出，fosh和fish一緻的字元串長度為3，fosh和fort一緻的字元串長度為2，是以使用者原本輸入的最可能是fish。