[站外圖片上傳中...(image-fe2902-1583294261806)]
什么是動(dòng)態(tài)規(guī)劃？
動(dòng)態(tài)規(guī)劃（Dynamic programming荆残，簡(jiǎn)稱(chēng)DP）啼肩，是一種通過(guò)“大而化小”的思路解決問(wèn)題的算法翎承。
動(dòng)態(tài)規(guī)劃沒(méi)有明確的算法模板硕盹，準(zhǔn)確的說(shuō)，它是一種思想叨咖。動(dòng)態(tài)規(guī)劃是一種解決問(wèn)題的思想瘩例。
什么樣的題目適用于動(dòng)態(tài)規(guī)劃
- 求最大值 / 最小值
- 求可不可行
- 求方案總數(shù)
以上三種問(wèn)題基本上都是用動(dòng)態(tài)規(guī)劃來(lái)求解。
注意：如果問(wèn)題是讓你求出“所有的”方案和結(jié)果甸各，則肯定不是使用動(dòng)態(tài)規(guī)劃垛贤。
動(dòng)態(tài)規(guī)劃問(wèn)題的解決過(guò)程
主要以3個(gè)子目標(biāo)來(lái)攻克此類(lèi)問(wèn)題：
- 建立狀態(tài)轉(zhuǎn)移方程。
- 緩存并復(fù)用以往結(jié)果趣倾。
- 按順序從小往大算南吮。
舉個(gè)簡(jiǎn)單的例子，1個(gè)人有2條腿誊酌，2個(gè)人有4條腿，...露乏，100 個(gè)人有多少條腿碧浊？
首先要建立狀態(tài)轉(zhuǎn)移方程： f(n) = 2n
這個(gè)太簡(jiǎn)單了不用緩存復(fù)用，直接計(jì)算即可瘟仿。
嘴上說(shuō)還是不夠的箱锐，我們用實(shí)際的問(wèn)題從淺到深，逐步來(lái)深入了解動(dòng)態(tài)規(guī)劃問(wèn)題劳较。
[Talk is cheap. Show me the code]
一驹止、斐波那契數(shù)列
斐波那契數(shù)列：0，1观蜗，1臊恋，2，3墓捻，5抖仅，8，13，21撤卢，34环凿，55，89放吩，144...
圖形如下：
[圖片上傳失敗...(image-cea13e-1583294261806)]
- 斐波那契數(shù)列規(guī)律計(jì)算公式如下：
[圖片上傳失敗...(image-208a66-1583294261806)]
- 先看看暴力遞歸方法：
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
if __name__ == "__main__":
result = fib(100)
print(result) # 別等了 根本執(zhí)行不出來(lái)
簡(jiǎn)單遞歸的時(shí)間復(fù)雜度達(dá)到了O(n2)智听。 因?yàn)槊看味家M(jìn)行重復(fù)計(jì)算。
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
可以看出渡紫，f(2) 計(jì)算了兩次到推，計(jì)算的n越大，循環(huán)的次數(shù)越多腻惠。
-
動(dòng)態(tài)規(guī)劃
In [20]: def fib(n): ...: result = list(range(n+1)) # 用于緩存以往結(jié)果环肘，以便復(fù)用（目標(biāo)2） ...: for i in range(n + 1): # 按順序從小往大算（目標(biāo)3） ...: if i < 2: ...: result[i] = i ...: else: # 使用狀態(tài)轉(zhuǎn)移方程（目標(biāo)1），同時(shí)復(fù)用以往結(jié)果（目標(biāo)2） ...: result[i] = result[i - 1] + result[i - 2] ...: return result[-1] # 輸出列表中最后一個(gè)數(shù)值集灌，也就是fib(n)的值 ...: In [21]: result = fib(100) In [22]: result Out[22]: 354224848179261915075L
- （目標(biāo)1）狀態(tài)轉(zhuǎn)移方程是什么: f(n) = f(n-1) + f(n-2)
- （目標(biāo)2）緩存并復(fù)用以往的結(jié)果悔雹。在
result[i]=result[i - 1]+result[i - 2]中進(jìn)行了復(fù)用。相當(dāng)于你在計(jì)算了 + 1 + 1 + 1 + 1 + 1 + 1 + 1= 7 之后欣喧，再 + 1 你可以很快的計(jì)算出是 8 腌零，不必再重新將 8 個(gè) 1 相加。 - （目標(biāo)3）從小到大計(jì)算唆阿。這樣以來(lái)益涧，時(shí)間復(fù)雜度降為
O(n)。我們只需要計(jì)算紅圈圈出的部分即可驯鳖。節(jié)省了大量的時(shí)間闲询。
二、不同路徑問(wèn)題
參照LeetCode上的62. 不同路徑
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）浅辙。
機(jī)器人每次只能向下或者向右移動(dòng)一步扭弧。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問(wèn)總共有多少條不同的路徑记舆？
上圖是一個(gè)7 x 3 的網(wǎng)格鸽捻。有多少可能的路徑？
太多了泽腮，我簡(jiǎn)化一個(gè)3 X 2 的御蒲。
解這道題的時(shí)候，我們也要從三個(gè)目標(biāo)開(kāi)始
-
（目標(biāo)1）狀態(tài)轉(zhuǎn)移方程是什么:
這道題你必須要知道轉(zhuǎn)移方程是什么诊赊。不然的話(huà)下面都不用做了...
f(i, j) = f(i-1, j) + f(i, j - 1) （目標(biāo)2）緩存并復(fù)用以往的結(jié)果厚满。這里是一個(gè)二維的行列問(wèn)題。我在這里用二維的數(shù)組解決這個(gè)問(wèn)題豪筝。
（目標(biāo)3）同樣也是從小到大計(jì)算痰滋。我們需要雙重循環(huán)摘能，逐行逐列進(jìn)行計(jì)算。
# encoding:utf8
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int m為行數(shù)
:type n: int n為列數(shù)
:rtype: int
"""
result = [[1] * n] * m
for i in range(1, m):
for j in range(1, n):
result[i][j] = result[i][j - 1] + result[i - 1][j]
return result[-1][-1]
if __name__ == '__main__':
s = Solution()
print s.uniquePaths(3, 7)
輸出結(jié)果為28敲街，證明我們的計(jì)算方法是正確的团搞。
三、01背包問(wèn)題
有n個(gè)物品多艇，它們有各自的體積和價(jià)值逻恐，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和峻黍？
為方便講解和理解复隆，下面講述的例子均先用具體的數(shù)字代入，即：eg：number＝4姆涩，capacity＝6
| i（物品編號(hào)） | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w（體積） | 2 | 3 | 4 | 5 |
| v（價(jià)值） | 3 | 4 | 5 | 6 |
背包問(wèn)題(0—1背包)
有N件物品挽拂，背包的最大承重為M，每件物品的數(shù)量均為1骨饿，價(jià)值集合為V亏栈，重量集合為W，計(jì)算該背包可以承載的物品的最大價(jià)值宏赘。
動(dòng)態(tài)規(guī)劃思想：
動(dòng)態(tài)規(guī)劃解題步驟：問(wèn)題抽象化绒北、建立模型、尋找約束條件察署、判斷是否滿(mǎn)足最優(yōu)性原理闷游、找大問(wèn)題與小問(wèn)題的遞推關(guān)系式、填表贴汪、尋找解組成
-
動(dòng)態(tài)規(guī)劃的原理：
- 動(dòng)態(tài)規(guī)劃與分治法類(lèi)似脐往，都是把大問(wèn)題拆分成小問(wèn)題，通過(guò)尋找大問(wèn)題與小問(wèn)題的遞推關(guān)系扳埂，解決一個(gè)個(gè)小問(wèn)題钙勃，最終達(dá)到解決原問(wèn)題的效果。
- 但不同的是：
- 分治法在子問(wèn)題和子子問(wèn)題等上被重復(fù)計(jì)算了很多次聂喇，
- 而動(dòng)態(tài)規(guī)劃則具有記憶性，通過(guò)填寫(xiě)表把所有已經(jīng)解決的子問(wèn)題答案紀(jì)錄下來(lái)蔚携，在新問(wèn)題里需要用到的子問(wèn)題可以直接提取希太，避免了重復(fù)計(jì)算，從而節(jié)約了時(shí)間酝蜒，所以在問(wèn)題滿(mǎn)足最優(yōu)性原理之后誊辉，用動(dòng)態(tài)規(guī)劃解決問(wèn)題的核心就在于填表，表填寫(xiě)完畢亡脑，最優(yōu)解也就找到堕澄。
-
背包問(wèn)題的解決過(guò)程
在解決問(wèn)題之前邀跃，為描述方便，首先定義一些變量：Vi表示第i個(gè)物品的價(jià)值蛙紫，Wi表示第i個(gè)物品的體積拍屑，定義V(i,j)：當(dāng)前背包容量j，前i個(gè)物品最佳組合對(duì)應(yīng)的價(jià)值坑傅，同時(shí)背包問(wèn)題抽象化（X1僵驰，X2，…唁毒，Xn蒜茴，其中Xi取0或1，表示第i個(gè)物品選或不選）浆西。此處要注意各個(gè)變量代表的含義粉私，尤其是
V(i,j)：當(dāng)前背包容量j，前i個(gè)物品最佳組合對(duì)應(yīng)的價(jià)值近零。
1诺核、建立模型，即求max(V1X1+V2X2+…+VnXn)秒赤；
2猪瞬、尋找約束條件，W1X1+W2X2+…+WnXn < capacity入篮；
3陈瘦、尋找遞推關(guān)系式，面對(duì)當(dāng)前商品有兩種可能性：
圖示：
| capacity | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | weight | value | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 0 | 0 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 4 | 0 | 0 | 3 | 4 | 4 | 7 | 7 |
| 3 | 4 | 5 | 0 | 0 | 3 | 4 | 5 | 7 | 8 |
| 4 | 5 | 6 | 0 | 0 | 3 | 4 | 5 | 7 | 8 |
# encoding:utf8
class Solution(object):
def bag01(self, weights, values, capacity):
# 動(dòng)態(tài)規(guī)劃
n = len(weights)
result = [[0 for j in range(capacity + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
result[i][j] = result[i - 1][j]
# 背包總?cè)萘繅蚍女?dāng)前物體潮售，遍歷前一個(gè)狀態(tài)考慮是否置換
if j >= weights[i - 1] and result[i][j] < result[i - 1][j - weights[i - 1]] + values[i - 1]:
result[i][j] = result[i - 1][j - weights[i - 1]] + values[i - 1]
for x in result:
print(x)
return result
def show(self, weights, capacity, result):
n = len(weights)
print ('最大解為：{}'.format(result[n][capacity]))
x = [False for i in range(n + 1)]
j = capacity
for i in range(n, 0, -1):
if result[i][j] > result[i - 1][j]:
# i代表第i個(gè)物品痊项，如果放入第i個(gè)物品的價(jià)值大于同等重量放入i-1物品的重量，說(shuō)明選擇了物品i
x[i] = True
j -= weights[i - 1]
print('items:')
for i in range(n + 1):
if x[i]:
print('no:{}'.format(i))
if __name__ == '__main__':
s = Solution()
weights = [2, 2, 3, 1, 5, 2]
values = [2, 3, 1, 5, 4, 3]
capacity = 10
result = s.bag01(weights, values, capacity)
s.show(weights, capacity, result)
輸出結(jié)果：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 0, 3, 3, 5, 5, 5, 5, 5, 5, 5]
[0, 0, 3, 3, 5, 5, 5, 6, 6, 6, 6]
[0, 5, 5, 8, 8, 10, 10, 10, 11, 11, 11]
[0, 5, 5, 8, 8, 10, 10, 10, 12, 12, 14]
[0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
最大解為：15
items:
no:2
no:4
no:5
no:6
Process finished with exit code 0
以上酥诽。
