[站外圖片上傳中...(image-fe2902-1583294261806)]
什么是動態(tài)規(guī)劃？
動態(tài)規(guī)劃（Dynamic programming，簡稱DP），是一種通過“大而化小”的思路解決問題的算法。
動態(tài)規(guī)劃沒有明確的算法模板，準(zhǔn)確的說，它是一種思想。動態(tài)規(guī)劃是一種解決問題的思想。
什么樣的題目適用于動態(tài)規(guī)劃
- 求最大值 / 最小值
- 求可不可行
- 求方案總數(shù)
以上三種問題基本上都是用動態(tài)規(guī)劃來求解。
注意：如果問題是讓你求出“所有的”方案和結(jié)果，則肯定不是使用動態(tài)規(guī)劃。
動態(tài)規(guī)劃問題的解決過程
主要以3個子目標(biāo)來攻克此類問題：
- 建立狀態(tài)轉(zhuǎn)移方程。
- 緩存并復(fù)用以往結(jié)果。
- 按順序從小往大算。
舉個簡單的例子，1個人有2條腿，2個人有4條腿，...，100 個人有多少條腿？
首先要建立狀態(tài)轉(zhuǎn)移方程： f(n) = 2n
這個太簡單了不用緩存復(fù)用，直接計(jì)算即可。
嘴上說還是不夠的，我們用實(shí)際的問題從淺到深，逐步來深入了解動態(tài)規(guī)劃問題。
[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í)行不出來
簡單遞歸的時間復(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ù)越多。
-
動態(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），同時復(fù)用以往結(jié)果（目標(biāo)2） ...: result[i] = result[i - 1] + result[i - 2] ...: return result[-1] # 輸出列表中最后一個數(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 個 1 相加。 - （目標(biāo)3）從小到大計(jì)算。這樣以來，時間復(fù)雜度降為
O(n)。我們只需要計(jì)算紅圈圈出的部分即可。節(jié)省了大量的時間。
二、不同路徑問題
參照LeetCode上的62. 不同路徑
一個機(jī)器人位于一個 m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑？
上圖是一個7 x 3 的網(wǎng)格。有多少可能的路徑？
太多了，我簡化一個3 X 2 的。
解這道題的時候，我們也要從三個目標(biāo)開始
-
（目標(biāo)1）狀態(tài)轉(zhuǎn)移方程是什么:
這道題你必須要知道轉(zhuǎn)移方程是什么。不然的話下面都不用做了...
f(i, j) = f(i-1, j) + f(i, j - 1) （目標(biāo)2）緩存并復(fù)用以往的結(jié)果。這里是一個二維的行列問題。我在這里用二維的數(shù)組解決這個問題。
（目標(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背包問題
有n個物品，它們有各自的體積和價值，現(xiàn)有給定容量的背包，如何讓背包里裝入的物品具有最大的價值總和？
為方便講解和理解，下面講述的例子均先用具體的數(shù)字代入，即：eg：number＝4，capacity＝6
| i（物品編號） | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w（體積） | 2 | 3 | 4 | 5 |
| v（價值） | 3 | 4 | 5 | 6 |
背包問題(0—1背包)
有N件物品，背包的最大承重為M，每件物品的數(shù)量均為1，價值集合為V，重量集合為W，計(jì)算該背包可以承載的物品的最大價值。
動態(tài)規(guī)劃思想：
動態(tài)規(guī)劃解題步驟：問題抽象化、建立模型、尋找約束條件、判斷是否滿足最優(yōu)性原理、找大問題與小問題的遞推關(guān)系式、填表、尋找解組成
-
動態(tài)規(guī)劃的原理：
- 動態(tài)規(guī)劃與分治法類似，都是把大問題拆分成小問題，通過尋找大問題與小問題的遞推關(guān)系，解決一個個小問題，最終達(dá)到解決原問題的效果。
- 但不同的是：
- 分治法在子問題和子子問題等上被重復(fù)計(jì)算了很多次，
- 而動態(tài)規(guī)劃則具有記憶性，通過填寫表把所有已經(jīng)解決的子問題答案紀(jì)錄下來，在新問題里需要用到的子問題可以直接提取，避免了重復(fù)計(jì)算，從而節(jié)約了時間，所以在問題滿足最優(yōu)性原理之后，用動態(tài)規(guī)劃解決問題的核心就在于填表，表填寫完畢，最優(yōu)解也就找到。
-
背包問題的解決過程
在解決問題之前，為描述方便，首先定義一些變量：Vi表示第i個物品的價值，Wi表示第i個物品的體積，定義V(i,j)：當(dāng)前背包容量j，前i個物品最佳組合對應(yīng)的價值，同時背包問題抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i個物品選或不選）。此處要注意各個變量代表的含義，尤其是
V(i,j)：當(dāng)前背包容量j，前i個物品最佳組合對應(yīng)的價值。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、尋找約束條件，W1X1+W2X2+…+WnXn < capacity；
3、尋找遞推關(guān)系式，面對當(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):
# 動態(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)前物體，遍歷前一個狀態(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個物品，如果放入第i個物品的價值大于同等重量放入i-1物品的重量，說明選擇了物品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
以上。
