動態規劃 無痛理解

前一陣子學習AlignedReID的論文。發現在DL的過程中還可以用DP解決最短路徑的對齊問題。就回過頭複習一下動態規劃。順便做一個小結，由於全都是自己理解的東西，沒有回頭對著書看公式，所以理解起來比較容易，但也許有不嚴謹之處。分為下面幾個小部分：

1.原理小結

2.湊硬幣問題（詳細）

3.切剛條問題 （略）

4.LCS（最長公共子序列） （略）

5.選個更難一點的例子 （詳細）

一.原理小結

動態規劃就是把一個大問題一步步降解成越來越小的子問題，直到子問題小到可以用確定的條件來解答。但是動態規劃的本質不是遞歸，遞歸是完全自頂而下的，每次求解都需要重新計算所有的子問題。我覺得反映動態規劃本質的解法是自底而上的解法，即按照順序，從基元問題一步步擴大問題的規模，直到問題的規模覆蓋了我要求解的問題。每一個規模的問題的解叫做一個狀態，每個不同規模的問題的解的關係叫做狀態轉移方程。具體的可以看湊硬幣問題的具體分析

二.湊硬幣問題

問題： 有1元、3元、5元面值的硬幣若干，要湊到11元需要最少幾個硬幣？

這是最簡單的DP問題，記湊a元需要b個硬幣為： n[a] = b。

1）首先，如果湊0元 需要0個硬幣表示為 n[0] = 0

2）如果湊1元: 我們最近拿硬幣的那次有三種可能 ：拿了1元、3元、5元。

於是問題表示為：n[1] = 1+n[0] 或者 1+n[-2]或者 1+n[-4]。是這三種情況的最小值。但是沒有湊-2或者湊-4元的情況，所以n[1] = 1+n[0]

3）湊2元：我們最近拿硬幣的那次有三種可能 ：拿了1元、3元、5元。

n[2] = min{ 1+n[1], 1+n[-1],1+n[-3] } = 1+n[1]，而n[1]已經從上一步知道了

4）湊3元....

湊4元.....

.......

湊11元： 我們最近拿硬幣的那次有三種可能 ：拿了1元、3元、5元。

n[11] = min{ 1+n[10], 1+n[8], 1+n[6] } ，這裡的n[10],n[8],n[6]在前幾步就已經被算出來了，所以我們在這一步只要求個最小值就好了。

每一個新的狀態都是由 「最近一個可能的動作」+「做該動作的上一個狀態」確定而轉移來的，這就是最基本的狀態轉移。這個問題的狀態轉移方程就可以看為：

n[m] = min{ 1+n[m-1], 1+n[m-3], 1+n[m-5] }

#最像偽代碼的寫法def coins(M): n = [0] for N in range(1,M+1): l = [] for i in [1,3,5]: if N-i >= 0: l.append(n[N-i]+1) n.append(min(l)) return n print(coins(11))#out:[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3]

當然從遞歸的角度，底頂而下，一次性的解決這個問題也是可以的。不過，遞歸的解法在每次需要用到子問題的結果時，即使剛剛算過這個子問題，它也會忘掉結果，重新把子問題遞歸到最底層求解，所以複雜度比較高。

def coins_rec(M): if M == 0: return 0 l = [] for i in [1,3,5]: if M - i >= 0: l.append( coins_rec(M-i)+1 ) return min(l) print(coins_rec(11))#out:3

回頭看剛剛的動態規劃寫法，其實這裡用到了一個memo，即代碼裡面的n[] 數組，來從小到大的儲存每一個已經解決的子問題的解，後面再需要用到該問題的解時，不需要重新算，讀出來就行了。下面我們比較一下兩種方法所用的時間。還是差距很大的。

如果想要輸出最小個數的同時輸出組合的面值，就每次記錄一下在 [1,3,5]這三個動作中，選取最小值時候使用的動作。

def cal_memo(M): n = [0] change = [0] process = [] for N in range(1,M+1): min_index = 100 min_number = 100 for i in [1,3,5]: if N-i >= 0: if n[N-i]+1 < min_number: min_index = i min_number = n[N-i]+1 n.append(min_number) change.append(min_index) index = M while(index >0 ): process.append(change[index]) index = index - change[index] return n[M],processprint(cal_memo(11))#out:(3, [1, 5, 5])

二.切剛條問題

問題：有一段長長的剛條可以切斷成若干節來賣，長度為0-10的剛條單獨賣的價格為：p = [0,1,5,8,9,10,17,17,20,24,30]。 問長度為n的剛條，最好的切割方法是什麼？

可以看出，長度為2的剛條單獨賣5元，切成2個長度為1的就只能賣2元了。而長度4的剛條9元，切成2個長度2的就是10元。所以貪心法是不對的。假設長度為n的剛條經過最優切割方案賣出的價格是 F[n]。可以把這個F[n]看成一個狀態。其實我在做DP的時候，喜歡先找狀態轉移的條件，就是每一步可以有的動作，這裡動作就是最近一次切下來長度為m的一部分，得到的新狀態可以用舊狀態表示為： F[n] = p[m]+F[n-m]，當然我們的m需要遍歷[1,2,....10] (n-m >= 0)。為什麼不要0？因為和之前的湊硬幣一樣的，我們從F[0],F[1]一步步擴展的，多切一小段長度1出來肯定多賣一點錢。

最像偽代碼的代碼，直接把擴展的過程print出來了。要輸出長度的組合和湊硬幣一樣，記錄一下每一步切割的長度就好

def Cut(n): p = [0,1,5,8,9,10,17,17,20,24,30] F = [0] for i in range(1,n+1): l = [] for m in range(1,11): if i-m >= 0: l.append(p[m] + F[i-m]) F.append(max(l)) print(i,F) return Fprint(Cut(20))

三.LCS問題

最長公共子序列問題：有X Y兩個序列，求最長的公共子序列的長度。舉例：

X: ABCBDAB

Y: BDCABA

最長的子序列為長度為4，有好幾條，比如：BDAB BCAB。

分析：基元的問題是x = X[:0], y = Y[:0]都是空序列，LCS(x,y) = 0。然後可以採取的動作是把X向後擴展一位或者把Y向後擴展一位。我們這裡就X：求LCS(X[:1],Y[:0] ) = 0發現擴X沒用的，Y[:0]是空的...所以LCS(X[:2],Y[:0] ) = 0....LCS[X,Y[:0]] = 0.我們這樣一步步刷過去，相當於在一個 len(Y)+1 * len(X)+1的表格裡面一行一行的從左到右算出每個A B部分對應的LCS。

在中間我們發現要填寫LCS( X[:i], Y[:j])時，自然想到

如果X[i] = Y[j]那麼LCS( X[:i], Y[:j]) = 1+LCS( X[:i-1], Y[:j-1]) 。而由於我們是一行行刷過來的，LCS( X[:i-1], Y[:j-1])求過了。

如果X[i] ！= Y[j]那麼LCS( X[:i], Y[:j]) = max{ LCS( X[:i], Y[:j-1]), LCS( X[:i-1], Y[:j]) }。這倆也都求出來了，所以這也就是一個填表的過程

一行一行從左到有填過來的。可以回頭找到好幾組不同的最長子序列。箭頭表示Y[i] = X[j]的狀態轉移。如果要print具體的子序列，就需要記錄一下i,j

最像偽代碼的代碼：

import numpy as npdef LCS(X,Y): table = np.zeros([len(Y)+1,len(X)+1]) for i in range(1, len(Y)+1): for j in range(1,len(X)+1): if Y[i-1] == X[j-1]: # 這裡-1是因為表格補了一行一列空元素，所以序號錯開了 table[i,j] = table[i-1,j-1]+1 else: table[i,j] = max( table[i,j-1], table[i-1,j]) return table LCS("ABCBDAB","BDCABA")

變一點點：如果要求連續的公共最長子序列。

如果X[i] = Y[j]那麼LCS( X[:i], Y[:j]) = LCS( X[:i-1], Y[:j-1])

如果X[i] ！= Y[j]那麼LCS( X[:i], Y[:j]) = 0，就相當於在這裡重新開始了。

四.詳解一個難一點的問題，沒有想好。。。