九章動態(tài)規(guī)劃背包型區(qū)間型瑞客論壇

1、動態(tài)專題第五講/掃描關(guān)注獲取最新面試題及權(quán)威解答: ninechapter知乎專欄：:官網(wǎng):本節(jié)大綱 背包動態(tài) 區(qū)間型動態(tài)例題Backpack IILintCode 125: Backpack II題意:給定N個物品，重量分別為正整數(shù)A0, A1, , AN-1，價值分別為正整數(shù)V0,V1, , VN-1一個背包最大承重是正整數(shù)M 最多能帶走多大價值的物品例子：輸入：4個物品，重量為2, 3, 5, 7，價值為1, 5, 2, 4. 背包最大承重是11輸出：9 （物品一+物品三，重量3+7=10，價值5+4=9）背包動態(tài)： 如何下手給定N個物品，重量分別為A0, A1, , AN-1，價值分別

2、為V0, V1, , VN-1一個背包最大承重是M每個裝物品的方案的總重量都是0到M如果對于每個總重量，我們能知道對應(yīng)的最大價值是多少，就能知道012M-2M-1M$10$8$0$3$5動態(tài)組成部分一：確定狀態(tài)和前一題類似，需要知道N個物品 是否能拼出重量W (W =0, 1, , M) 對于每個重量W，最大總價值是多少：最后一個物品（重量AN-1, 價值VN-1）是否進入背包最012M-2M-1M$0$3$5$10$8選擇二：如果前N-1個物品能拼出W- AN-1，最大總價值是V，則再加上最后一個物品(重量AN-1, 價值VN-1)，能拼出W，總價值是V+VN-1選擇一：如果前N-1個物品能

3、拼出W，最大總價值是V，前N個物品也能拼出W并且總價值是V動態(tài)組成部分一：確定狀態(tài)例子：3個物品，重量為2, 3, 5, 價值為10, 20, 50前2個物品可以拼出重量5 (2+3) ，最大價值是30 (10+20)，前3個物品也可以拼出重量5，價值30前2個物品可以拼出重量0，價值0，加上最后一個物品，可以拼出重量5， 價值50，50>30，所以所有物品拼出重量5時，最大總價值是500kg, $05kg, $305kg$505kg$503kg$203kg$202kg$102kg$10選擇一選擇二動態(tài)組成部分一：確定狀態(tài)例子：3個物品，重量為2, 3, 5, 價值為10, 20, 50

4、前2個物品可以拼出重量5 (2+3) ，最大價值是30 (10+20)，前3個物品也可以拼出重量5，價值30前2個物品可以拼出重量0，價值0，加上最后一個物品，可以拼出重量5， 價值50，50>30，所以所有物品拼出重量5時，最大總價值是505kg, $505kg, $305kg$505kg$503kg$203kg$202kg$102kg$10選擇一選擇二子問題要求前N個物品能不能拼出重量0, 1, , M，以及拼出重量W能獲得的最大價值需要知道前N-1個物品能不能拼出重量0, 1, , M，以及拼出重量W能獲得的最大價值子問題狀態(tài)：設(shè)fiw = 用前i個物品拼出重量w時最大總價值(-1

5、表示不能拼出w)動態(tài)組成部分三：轉(zhuǎn)移方程 設(shè)fiw = 用前i個物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxfi-1w, fi-1w-Ai-1 + Vi-1 | wAi-1 且fi-1w-Ai-1 -1用前i-1個物品拼出重量w-Ai-1 時最大總價值，加上第i個物品用前i-1個物品拼出重量w時最大總價值用前i個物品拼出重量w時最大總價值動態(tài)組成部分三：初始條件和邊界情況設(shè)fiw = 用前i個物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxfi-1w, fi-1w-Ai-1 + Vi-1 | wAi-1 且fi-1w-Ai-1 -1初始條件： f00

6、 = 0: 0個物品可以拼出重量0，最大總價值是0 f01.M = -1: 0個物品不能拼出大于0的重量邊界情況： fi-1w-Ai-1只能在wAi-1，并且fi-1w-Ai-1 -1時使用動態(tài)組成部分四：計算順序初始化f00, f01, , f0M計算前1個物品拼出各種重量的最大價值：f10, f11, , f1M計算前N個物品拼出各種重量的最大價值：fN0, fN2, , fNM：max0<=j<=MfNj | fNj -1時間復(fù)雜度（計算步數(shù)）：O(MN)，空間復(fù)雜度（數(shù)組大?。簝?yōu)化后可以達到O(M)編程例題Backpack IIILintCode 440: Backpac

7、k III題意:給定N種物品，重量分別為正整數(shù)A0, A1, , AN-1，價值分別為正整數(shù)V0,V1, , VN-1每種物品都有無窮多個一個背包最大承重是正整數(shù)M最多能帶走多大價值的物品例子：輸入：4個物品，重量為2, 3, 5, 7，價值為1, 5, 2, 4. 背包最大承重是10輸出：15 （3個物品一，重量3*3=9，價值5*3=15）背包動態(tài)： 如何下手和上一題唯一的不同是：每種物品都有無窮多個一個背包最大承重是MBackpack II的轉(zhuǎn)移方程設(shè)fiw = 用前i個物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxfi-1w, fi-1w-Ai-1 + Vi-1用

8、前i-1個物品拼出重量w-Ai-1 時最大總價值，加上第i個物品用前i-1個物品拼出重量w時最大總價值用前i個物品拼出重量w時最大總價值背包動態(tài)： 如何下手因為Ai-1有無窮多個，所以可以用0個Ai-1，1個Ai-1 ，2個Ai-1 ，Backpack II的轉(zhuǎn)移方程設(shè)fiw = 用前i個物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxfi-1w, fi-1w-Ai-1 + Vi-1用前i-1個物品拼出重量w-Ai-1 時最大總價值，加上第i個物品用前i-1個物品拼出重量w時最大總價值用前i個物品拼出重量w時最大總價值動態(tài)組成部分二：轉(zhuǎn)移方程因為Ai有無窮多個，所以可以用0

9、個Ai ，1個Ai ，2個Ai ，Backpack III的轉(zhuǎn)移方程設(shè)fiw = 用前i種物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxk>=0fi-1w-kAi-1 + kVi-1用前i-1種物品拼出重量w-kAi-1 時最大總價值，加上k個第i種物品用前i種物品拼出重量w時最大總價值Backpack III優(yōu)化設(shè)fiw = 用前i種物品拼出重量w時最大總價值 (-1表示不能拼出w)fiw = maxfi-1w, fi-1w-Ai-1 + Vi-1, fi-1w-2Ai-1 + 2Vi-1,fiw = maxfi-1w, fiw-Ai-1 + Vi-1用前i種物品

10、拼出重量w-Ai-1 時最大總價值，加上第i個物品用前i-1種物品拼出重量w時最大總價值用前i種物品拼出重量w時最大總價值用前i-1種物品拼出重量w-Ai-1 時最大總價值，加上第i個物品用前i-1種物品拼出重量w時最大總價值用前i種物品拼出重量w時最大總價值動態(tài)組成部分四：計算順序fiw = maxfi-1w, fiw-Ai-1 + Vi-1實際編程中可以進一步優(yōu)化w=01234567i=0i=1i=2i=3動態(tài)組成部分四：計算順序fiw = maxfi-1w, fiw-Ai-1 + Vi-1實際編程中可以進一步優(yōu)化w=01234567i=0i=1i=2i=3編程小結(jié)Backpack 可行性

11、背包 題面：要求不超過Target時能拼出的最大重量最大承重14公斤fiw=前i個物品能不能拼出重量wBackpack V, Backpack VI, 計數(shù)型背包 題面：要求有多少種方式拼出重量Targetfiw=前i個物品有多少種方式拼出重量wBackpack II, Backpack III, 最值型背包 題面：要求能拼出的最大價值fiw=前i個/種物品拼出重量w能得到的最大價值關(guān)鍵點 最 最后一個背包內(nèi)的物品是哪個 最后一個物品有沒有進背包 數(shù)組大小和最大承重Target有關(guān)空間優(yōu)化10kg$405kg$103kg$403kg$20區(qū)間型動態(tài)給定一個序列/字符串，進行一些操作會將序列/字

12、符串去頭/去尾最剩下的會是一個區(qū)間i, j狀態(tài)自然定義為fij，表示面對子序列i, , j時的最優(yōu)性質(zhì)例題Longest Palindromic SubsequenceLintCode 667 Longest Palindromic Subsequence題意：給定一個字符串S，長度是N找到它最長的序列的長度例子：輸入： “bbbab”輸出： 4 (“bbbb”)動態(tài)組成部分一：確定狀態(tài)串T，長度是M最優(yōu)策略產(chǎn)生最長的情況1：回文串長度是1，即一個字母情況2：回文串長度大于1，那么必定有T0=TM-1動態(tài)組成部分一：確定狀態(tài)串T，長度是M最優(yōu)策略產(chǎn)生最長的情況1：回文串長度是1，即一個字母情況

13、2：回文串長度大于1，那么必定有T0=TM-1S012N-4N-3N-2N-1TT0TM-1dxbgabb動態(tài)組成部分一：確定狀態(tài)設(shè)T0是Si, TM-1是SjT剩下的部分T1.M-2仍然是一個回文串，而且是Si+1.j-1的最長串S0i=12N-4N-3j=N-2N-1TT0TM-1dxbgabb子問題要求Si.j的最長串如果Si=Sj，需要知道Si+1.j-1的最長串是Si+1.j的最長串或Si.j-1的最長否則子問題串狀態(tài)：設(shè)fij為Si.j的最長串的長度S0i=12N-4N-3j=N-2N-1TT0TM-1dxbgabb動態(tài)組成部分二：轉(zhuǎn)移方程 設(shè)fij為Si.j的最長串的長度fij

14、= maxfi+1j, fij-1, fi+1j-1 + 2|Si=Sj Si+1.j的最長回 Si.j-1的最長回 Si+1.j-1的最長串 的長度，加上Si和Sj的長度的長度Si.j的最長回文子串的長度動態(tài)組成部分三：初始條件和邊界情況設(shè)fij為Si.j的最長串的長度fij = maxfi+1j, fij-1, fi+1j-1 + 2|Si=Sj初始條件 f00 = f11 = = fN-1N-1 = 1 一個字母也是一個長度為1的回文串 如果Si = Si+1, fii+1 = 2 如果Si != Si+1, fii+1 = 1動態(tài)組成部分四：計算順序設(shè)fij為Si.j的最長串的長度fi

15、j = maxfi+1j, fij-1, fi+1j-1 + 2|Si=Sj不能按照i的順序去算：按照長度j-i從小到大的順序去算區(qū)間動態(tài)動態(tài)組成部分四：計算順序012N-4N-3N-2N-1dxbgabb動態(tài)組成部分四：計算順序長度1：f00, f11, f22, , fN-1N-1長度2： f01, , fN-2N-1長度N： f0N-1是f0N-1時間復(fù)雜度O(N2)，空間復(fù)雜度O(N2)編程記憶化搜索動態(tài)編程的另一個選擇fij = maxfi+1j, fij-1, fi+1j-1 + 2|Si=Sj計算f(0, N-1)遞歸計算f(1, N-1), f(0, N-2), f(1, N-

16、2)記憶化: 計算f(i, j)結(jié)束后，將結(jié)果保計算f(i, j)，直接返回fij數(shù)組fij里，下次如果需要再次記憶化搜索f(0,10)f(0, 9)f(1,10)f(1, 9)f(0, 8)f(1, 9)f(1, 8)f(1, 9)f(2,10)f(2, 9)f(2, 9)f(1, 8)f(2, 8)記憶化搜索f(0,10)f(0, 9)f(1,10)f(1, 9)f(0, 8)f(1, 9)f(1, 8)f(1, 9)f(2,10)f(2, 9)f(2, 9)f(1, 8)f(2, 8)與遞推比較自下而上：f0, f1, , fN遞推自上而下：f(N), f(N-1), 記憶化記憶化搜索編

17、寫一般比較簡單所有f值遞推在某些條件下可以做空間優(yōu)化，記憶化搜索則必須編程 課間休息5分鐘 課程問卷例題Coins In A Line IIILintCode 396 Coins In A Line III題意：給定一個序列a0, a1, , aN-1兩個玩家Alice和Bob輪流取數(shù)每個人每次只能取第一個數(shù)或最后一個數(shù)雙方都用最優(yōu)策略，使得問先手是否必勝 如果數(shù)字和一樣，也算先手勝的數(shù)字和盡量比對手大例子：輸入：1, 5, 233, 7輸出：True （先手取走1，無論后手取哪個，先手都能取走233）博弈這題是一道博弈題，目標是讓拿到的數(shù)字之和不比對手小設(shè)己方數(shù)字和是A，對手數(shù)字和是B，即目

18、標是A>=B等價于A-B>=0也就是說，如果Alice和Bob都存著分別記為SA=A-B， SB=B-A的數(shù)字和與對手的數(shù)字和之差，則Alice的目標是最大化SA，Bob的目標是最大化SB博弈當一方X面對剩下的數(shù)字，可以認為X就是當前的先手，他的目標就是最大化SX=X-Y當他取走一個數(shù)字m后，對手Y變成先手，同理他也要最大化SY=Y-X對于X來說，SX = -SY + m其中，m是當前這步的數(shù)字，-SY是對手看來的數(shù)字差取相反數(shù)（因為先手是X）現(xiàn)在X有兩種選擇，取第一個數(shù)字m1或最后一個數(shù)字m2，為了最大化SX， 應(yīng)該選擇較大的那個SX動態(tài)組成部分一：確定狀態(tài)如果Alice第一步取

19、走a0，Bob面對a1.N-1Bob的最大數(shù)字差是SYAlice的數(shù)字差是a0-SY如果Alice第一步取走aN-1，Bob面對a0.N-2Bob的最大數(shù)字差是SYAlice的數(shù)字差是aN-1-SYAlice選擇較大的數(shù)字差博弈子問題當Bob面對a1.N-1，他這時是先手）和后手（Alice）的數(shù)字差他的目標同樣是最大化先手（但是此時的數(shù)字少了一個：a1.N-1子問題狀態(tài)：設(shè)fij為一方先手在面對ai.j這些數(shù)字時，能得到的最大的與對手的數(shù)字差動態(tài)組成部分二：轉(zhuǎn)移方程 設(shè)fij為一方在面對ai.j這些數(shù)字時，能得到的最大的與對手的數(shù)字差fij = maxai - fi+1j, aj - fij

20、-1選擇aj，對手采取最優(yōu)策略時 能得到的最大的與對手的數(shù)字差選擇ai，對手采取最優(yōu)策略時 能得到的最大的與對手的數(shù)字差為一方在面對ai.j時， 能得到的最大的與對 手的數(shù)字差動態(tài)組成部分三：初始條件與邊界情況設(shè)fij為一方在面對ai.j這些數(shù)字時，能得到的最大的與對手的數(shù)字差fij = maxai-fi+1j, aj-fij-1只有一個數(shù)字ai時，己方得ai分，對手0分，數(shù)字差為ai fii = ai (i=0, 1, , N-1)動態(tài)組成部分四：計算順序長度1：f00, f11, f22, , fN-1N-1長度2： f01, , fN-2N-1長度N： f0N-1如果f0N-1>=

21、0，先手Alice必贏，否則必輸時間復(fù)雜度O(N2)，空間復(fù)雜度O(N2)編程例題Scramble StringLintCode 430 Scramble String題意：給定一個字符串S，按照樹結(jié)構(gòu)每次二分成左右兩個部分，直至單個字符在樹上某些節(jié)點交換左右兒子，可以形成新的字符串一個字符串T是否由S經(jīng)過這樣的變換而成例子：輸入：S=“great” T=“rgtae”輸出：True動態(tài)組成部分一：確定狀態(tài)顯然，T如果長度和S不一樣，那么肯定不能由S變換而來如果T是S變換而來的，并且我們知道S最上層二分被分成S=S1S2，那么一定有： T也有兩部分T=T1T2，T1是S1變換而來的，T2是S2

22、變換而來的 T也有兩部分T=T1T2，T1是S2變換而來的，T2是S1變換而來的情況一情況二T2T1S2S1T1T2S1S2T2T1S2S1T1T2S1S2子問題要求T是否由S變換而來需要知道T1是否由S1變換而來的，T2是否由S2變換而來需要知道T1是否由S2變換而來的，T2是否由S1變換而來S1, S2, T1, T2長度更短子問題狀態(tài)：fijkh表示Tk.h是否由Si.j變換而來動態(tài)組成部分一：確定狀態(tài)這里所有串都是S和T的子串，且長度一樣所以每個串都可以用(起始位置，長度)表示例如： S1長度是5，在S中位置7開始 T1長度是5，在T中位置0開始 可以用f705=True/False表

23、示S1能否通過變換成為T1狀態(tài)：設(shè)fijk表示S1能否通過變換成為T1 S1為S從字符i開始的長度為k的子串 T1為T從字符j開始的長度為k的子串動態(tài)組成部分二：轉(zhuǎn)移方程 設(shè)fijk表示S1能否通過變換成為T1 S1為S從字符i開始的長度為k的子串 T1為T從字符j開始的長度為k的子串fijk = OR1<=w<=k-1fijw AND fi+wj+wk-wOROR1<=w<=k-1fij+k-ww AND fi+wjk-w動態(tài)組成部分三：初始條件和邊界情況 設(shè)fijk表示S1能否通過變換成為T1 S1為S從字符i開始的長度為k的子串 T1為T從字符j開始的長度為k的子

24、串 如果Si=Tj，fij1=True，否則fij1=False動態(tài)組成部分四：計算順序設(shè)fijk表示S1能否通過變換成為T1 S1為S從字符i開始的長度為k的子串 T1為T從字符j開始的長度為k的子串按照k從小到大的順序進行計算 fij1，0<=i<N, 0<=j<N fij2，0<=i<N-1, 0<=j<N-1 f00N是f00N時間復(fù)雜度O(N4)，空間復(fù)雜度O(N3)編程例題Burst BalloonsLintCode 168 Burst Balloons題意：給定N個氣球，每個氣球上都標有一個數(shù)字：a1, a2, , aN第i個氣球可以獲得aleft*ai*aright枚金幣要求所有氣球， left和right是與i相鄰的下標氣球i以后，left和right就變成相鄰的氣球求最多獲得的金幣數(shù)（設(shè)a0=aN+1=1）例子：輸入：3, 1, 5, 8輸出：167 3,1,5,8 à 3,5,8 à 3,8 à 8 à 金幣3*1*5 + 3*5*8 + 1