動態規劃的基本思想
將一個問題劃分為多個不獨立的子問題,這些子問題在求解過程中可能會有些數據進行了重復計算。我們可以把計算過的數據保存起來,當下次遇到同樣的數據計算時,就可以查表直接得到答案,而不是再次計算
動態規劃的例子
找兩個字符串匹配的編輯距離
字符串的編輯距離,又稱為Levenshtein距離,是指利用字符操作,把字符串A轉換成字符串B所需要的最少操作數。操作包括增刪改
**問題:**給定兩個字符串A:sun和B:sautr,求字符串A至少經過多少步字符操作變成字符串B
解:
用<i,j>表示字符串A長為i,字符串B長為j的字符串編輯距離
對兩個字符串,最末位字符進行討論
相同:那么末位字符不需要進行操作,那么<i,j>=<i-1,j-1>
不相同:
可以做三種操作:
Ⅰ:增加一個字符:
增加后,末尾字符相同,問題變成i+1長的字符串A與j長的字符串B匹配
<i,j>=<i+1,j>+1,+1是此次做的增加操作
又由上可知<i,j>=<i-1,j-1>,所以
<i,j>=<i,j-1>+1
Ⅱ:刪
同理,<i,j>=<i-1,j>+1
Ⅲ:改
同理,<i,j>=<i-1,j-1>+1
做矩陣圖,<i,j>框內數字表示A前i個字符與B前j個字符匹配時,最小修改次數,由圖可知,確定它的最小值,如果末尾字符相同,則等于左側對角線值,不相等,則從周圍三個數值中,選最小的+1
背包問題
**問題:**有n個物品,它們有各自的體積和價值,現有給定容量的背包,如何讓背包里裝入的物品具有最大的價值總和?
假設現在有四個物品,背包容量為8
i(編號) 1 2 3 4
w(體積) 2 3 4 5
v(價值) 3 4 5 6
解:
矩陣圖中<i,j>表示從下標為 [0 - i] 的物品里任意取,放進容量為j的背包,價值總和最大是多少。
每次我們有兩種選擇:
將物品放入背包:加該物品的重量和價值
不放入:保持原來的數值
如果容量為3,可以選擇的物品有1,2,3
那么我們只需要比較<i-1,j>,<i-1,j-w(i))>+v(i)
其中<i-1,j>表示不裝該物品,<i-1,j-w(i))>+v(i) 表示裝了該商品,背包容量減少w(i),但價值增加了v(i);
取兩者中最大值即可