LeetCode Dynamic Programming DP

九章DP班歸納:

• 坐標型DP：保存的是坐標的狀態(tài)傲茄；
• 序列型DP：保存的是前x個的狀態(tài)（數(shù)組或cache會多開一個0狀態(tài)）
• 劃分型DP：同序列性技即；最后一個狀態(tài)=最后一段；指定段數(shù)=> 二維狀態(tài)，不指定=> 一維
• 博弈型DP：就是A的win會導致B的lose
• 背包型DP：要保存每個重量w作為狀態(tài)瀑焦，大多數(shù)能滾動數(shù)組優(yōu)化空間序仙。
• 區(qū)間型DP：維護兩個狀態(tài)，序列首i丧枪，序列尾j。計算順序必須是按序列長度j-i+1

7.6
120. Triangle: 最簡單動態(tài)規(guī)劃庞萍，記住要用cache拧烦。

7.8
62. Unique Paths: 用cache。
63. Unique Paths II: cache钝计，只不過障礙物的路徑=0即可恋博。
70. Climbing Stairs: cache水題
746. Min Cost Climbing Stairs: 必須DP，簡單題犯傻

7.9
300. Longest Increasing Subsequence: 對動態(tài)規(guī)劃應該有些許理解

7.10

354. Russian Doll Envelopes: LIS的變種葵蒂，二維數(shù)組排序時交播，需要將第二個元素倒序排列。其實LIS是一個深坑践付，詳情見下網(wǎng)址：

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

在這里對LIS進行短暫說明秦士，如 1,3,2,5,4。

• 首先是DP法永高，進行一次for循環(huán)隧土，獲取i位置的LIS（末尾必須為nums[i]），比如nums[i]=4的話命爬，那么4的LIS(4) = max(LIS(1),LIS(2),LIS(3)) +1 = LIS(3) + 1 = LIS(1) + 2 = 3曹傀。將LIS函數(shù)作為DP函數(shù)，維護一個cache即可饲宛。那么這樣的時間復雜度皆愉，最壞為O(n^{2)，最好仍為O(n}2),空間復雜度穩(wěn)定為O(n)。

• 然后是Patience sorting（耐心排序法）幕庐，這個算法類似于桶排序久锥。整個算法進行一次遍歷，每次只取建桶和入桶兩種操作的一種异剥。規(guī)則如下：當元素e比每個桶的的末尾值都大時瑟由，新建一個桶存放e；如果e比一些桶的末尾值還小冤寿，取這些末尾值的最小值歹苦，e入最小末尾桶。對應例子督怜，1殴瘦、3都各自建桶([1],[3])，之后2只能入3的桶([1],[3,2])号杠，5單獨建桶([1],[3,2],[5])痴施，4只能入5的桶([1],[3,2],[5,4])。最后結(jié)果等于桶的個數(shù)究流。時間復雜度，最壞為O(n^2)动遭，最好O(n)芬探，空間復雜度最壞O(n),最好為O(1)。

• 補充 - 耐心排序優(yōu)化和證明：

• 優(yōu)化：顯然每次操作檢查末尾值的時候厘惦，所有末尾值也是升序序列偷仿，如例子中的1,3/1,2/1,2,5/1,2,4。那這就可以使用二分查找宵蕉，而非順序查找了酝静。時間復雜度最壞降至O(nlogn)。

• 證明：弱對偶性：桶的數(shù)量>=LIS羡玛，因為桶是按照原數(shù)組降序排列的别智，那么不能使用同一個桶一個以上的數(shù)（原本他們就不符合升序，你抽出來就違反規(guī)則了）稼稿。所以LIS不會超過桶的數(shù)量薄榛；強對偶性：那可不可以不取某個桶的一個數(shù)，獲得LIS呢让歼？不行敞恋。因為每個桶內(nèi)部始終是降序的，而每個桶的末尾形成的數(shù)組是升序的谋右。那么建桶時硬猫，這個數(shù)的位置是根據(jù)之前桶末尾的最大值確定，可以看成一個指針指向這個最大值。入桶啸蜜，同樣也是指向了之前的一個桶末尾（不一定最大坑雅，但可以是一個桶）。那么除了第一個元素盔性，所有數(shù)都有一個前置指針霞丧，不存在孤立的桶，LIS不能小于桶數(shù)冕香。根據(jù)弱對偶性蛹尝，不能大于，只能等于悉尾，證畢突那。

368. Largest Divisible Subset: 沒有想象那么復雜，就是單純的Cache DP构眯。
139. Word Break: Cache DP愕难，middle真的不難。
140. Word Break II: I的基礎上加DFS惫霸，最騷的是DP居然寫錯了猫缭。

7.11
32. Longest Valid Parentheses: DP狀態(tài)轉(zhuǎn)換相當難。

• 左括號不保存狀態(tài)壹店，始終為0猜丹。

• i坐標產(chǎn)生'()'時，狀態(tài)加2硅卢，原狀態(tài)坐標為i-2射窒；

• 產(chǎn)生'))'時，先計算i-1的狀態(tài)将塑，獲得最優(yōu)解last脉顿，比如最優(yōu)解是4那么可能是'...()())'，則判斷i - last - 1是否為’(‘点寥。

• 是艾疟，則整個滿足狀態(tài)更新，last + 2 + DP(last - 1),后面這個是關(guān)鍵;

• 否开财，狀態(tài)不滿足汉柒，清0.

7.12
44. Wildcard Matching: 難，看了參考答案责鳍，必須用數(shù)組DP碾褂，不然會MLE。

• 為了把空串包含進去历葛，維護一個m+1,n+1的矩陣正塌。0行和0列嘀略，表示s或p是空串。

• 空串能匹配空串乓诽，所以DP[0][0] = True帜羊，空串不能匹配任何非空串，所以DP[0][j] = False鸠天。

• 初始化DP[i][0]讼育，如果DP[i-1][0]成功匹配，且p[i-1]=='*',則DP[i][0] = True稠集。

• 狀態(tài)轉(zhuǎn)移奶段，匹配p[i-1]和s[j-1]，如果p是字符或者通用字符'?'剥纷，則正常匹配s[i-1]痹籍，成功則返回DP[i-1][j-1]；如果p是'*',則有三種情況：

• *不匹配任何字符晦鞋，返回DP[i-1][j]

• *匹配一個字符,返回DP[i-1][j-1]

• *匹配多個字符蹲缠，返回DP[i][j-1] （跳過s的一個字符）

322. Coin Change: DP Cache。

7.17
403. Frog Jump: 超難題悠垛，重點是狀態(tài)轉(zhuǎn)移是多重的线定，每個key需要保存的是步數(shù)，而不是終點确买。因為同一個終點渔肩，可能由多個路徑變化而來，沒法獲得狀態(tài)轉(zhuǎn)移方程拇惋。

7.18
LintCode 515. Paint House: 沒啥難點的基本題。

7.19
91. Decode Ways: 坑點很多的dp題抹剩，劃分性DP撑帖。我的做法：i=0且s[i]=0，則直接返回0了澳眷，否則返回1; 通常情況dp[i] = dp[i-1]胡嘿，如果s[i-1]=1或者（s[i-1]=2且s[i]<7），則dp[i] = dp[i-1]+dp[i-2]钳踊。邊界情況衷敌，i<0，返回1（解釋：必定是i=1時會觸發(fā)下個dp的i<0拓瞪，且前面的數(shù)是非0的缴罗，比如17。那么此時對應的情況是兩種祭埂，所以返回1即可）面氓。
64. Minimum Path Sum: 很簡單的DP兵钮，不用cache都行。

7.21
553. Bomb Enemy: 要四個方向進行DP舌界，保存這個節(jié)點所在的方向有幾個敵人掘譬。坐標型DP
338. Counting Bits: 類似坐標型DP，難點主要是用java呻拌，不熟葱轩。

7.22
LintCode 516. Paint House II： 我用了兩個cache，其中一個minCache保存上一代最小的兩個數(shù)字藐握，這樣就不用提取所有的上一代了靴拱。（果然答案是這個，腦筋急轉(zhuǎn)彎爸和蕖缭嫡？）

7.23
198. House Robber: 真的很簡單...
213. House Robber II: 循環(huán)版的，我是開的兩個初始點抬闷，注意：要特殊處理前三個點妇蛀，因為雖然最后一個點不可以從第一個點開始跳，但它可以從第三個點開始跳笤成。<u>> 簡單做法评架，直接掐頭或者去尾，分成兩種情況的House Robber炕泳。</u>

7.24
337. House Robber III: 樹版的纵诞，思路不難，但是要記住用cache培遵。
121. Best Time to Buy and Sell Stock: 沒看出來用DP浙芙，DP法是DP[i]保存第i天賣能獲得的最大利潤。
122. Best Time to Buy and Sell Stock II: 用的貪心籽腕，記住等于的情況直接強行更新了嗡呼。媽的，直接遇到i+1 > i的皇耗，累計差值就行了...

7.26

123. Best Time to Buy and Sell Stock III: 超難DP南窗，階段轉(zhuǎn)移+序列轉(zhuǎn)移。與之前不同郎楼，最多只能兩次交易万伤。提出階段這一概念，具體如下呜袁。
所以保存狀態(tài)f[i][j], i表示該股票在前i天的獲利敌买，j表示所在階段。

• 初始狀態(tài)：f[0][0] = 0, f[0][j] (j > 0) = 負無窮;

• 轉(zhuǎn)移方程：

• f[i][0] (i > 0) = f[i-1][0]阶界，階段1只能掛機觀望;

• f[i][1] = max(f[i-1][1] + P[i-1] - P[i-2], f[i-1][0])：

• 分析：第一項表示昨天就買入了放妈，今天繼續(xù)持有北救，并且獲得當天紅利（可能為負）；第二項表示昨天還沒有買入芜抒，今天就買入了珍策，所以暫時沒有任何獲利，只是狀態(tài)轉(zhuǎn)移了宅倒。

• 例子：3攘宙，2，5拐迁。f[1][1] = f[0][0] = 0 蹭劈，得 f[2][1] = max(f[1][1] + P[1] - P[0] , f[1][0]) = max(-1,0) = 0，所以第二天進入階段2只能是當天買线召，而不是在第一天買铺韧。

• f[i][2] = max(f[i-1][1] + P[i-1] - P[i-2], f[i-1][2])：

• 分析：第一項表示昨天還在持有，今天就拋出了缓淹，并獲得當天紅利哈打；第二項，昨天已經(jīng)拋出了讯壶，今天仍不買入料仗；

• f[i][3] = max(f[i-1][3] + P[i - 1] - P[i - 2], f[i-1][2], f[i-1][1] + P[i-1] - P[i - 2])

• 分析：這個比f[i][1]多一項，這一項表示從階段2賣出后馬上買入伏蚊，跳過階段3的觀望立轧。

• f[i][4] = max(f[i-1][3] + P[i - 1] - P[i - 2], f[i-1][4])

• 同f[i][2]

總結(jié)：這個題基本表現(xiàn)了Hard DP的一些特點，首先序列DP（第一維）是必須的躏吊，表示了要求的東西是什么（這道題是最大收益）氛改；其次第二維是階段，這種題還沒復雜到圖的轉(zhuǎn)移比伏，階段轉(zhuǎn)移是單向的平窘，但是每個階段的轉(zhuǎn)移需要你至少去分析前面兩個階段，且每種轉(zhuǎn)移方程都是不完全一樣的凳怨。多做一些這種題，或許可以攻破DP是鬼。

7.29
188. Best Time to Buy and Sell Stock IV: 這題不能直接用III的思路套肤舞，因為其實3的解法只是清晰，而不是最優(yōu)的均蜜。

• 首先李剖，k可以非常大，那么當大到可以隨時交易（k>len(prices)/2)了囤耳，就用II的解法篙顺，遇到上升就保存偶芍。這樣能避免一些極端testcase；

• 其次用兩個數(shù)組德玫，或者長度為2的二維數(shù)組就行了匪蟀；

• 使用新的轉(zhuǎn)移方程：兩個數(shù)組分別為buy和sell，表示第k次買或賣的利潤宰僧，但是外循環(huán)材彪，每一支股票對全局進行更新。

• buy[j] = min(prices[i] - sell[j-1], buy[j])琴儿，表示對于股票i段化，第j次買，我用sell[j-1]的積蓄買了造成，是不是比前i-1支股票的第j次買便宜显熏；如果是就更新，不是就跳過晒屎；

• sell[j] = min(prices[i] - buy[j], sell[j])喘蟆，同理，第j次賣夷磕，我是以prices[i] - buy[i]的價格套利履肃，還是不管這支股票呢；

• 時間復雜度O(kn)或O(n),空間復雜度O(k)坐桩。

8.1
279. Perfect Squares: 其實是比較簡單的DP尺棋，亮點是python過不了。
LintCode 108. Palindrome Partitioning II: 較難DP绵跷，要DP先確定是否是回文串（如果這里不用DP膘螟，那么就會讓時間復雜度增加到O(n^{3)，然后再DP計算劃分次數(shù)（總體時間復雜度O(n}2)）碾局。另外一個結(jié)論是荆残，盡量別用hashset，開銷比array大不少净当。

8.3
LintCode 437. Copy Books: 較難dp内斯，狀態(tài)轉(zhuǎn)移包括minmax，具體轉(zhuǎn)移方程是f[i][j] (i表示前i個人像啼，j表示前j本書）：
f[i][j] = min(max(f[i-1][p],A[p]+ ... + A[j-1]), max...) for p in [0,j)
LintCode 394. Coins in a Line：簡單博弈性DP俘闯，你的負等于上家的只能勝。
LintCode 92. Backpack: 背包問題忽冻，屬于特殊性DP真朗。雙狀態(tài)，一個維護查看了多少個物品i不必多說僧诚，另外一個狀態(tài)維護的是0~m總重量遮婶，保存的是能否拼出這個重量j蝗碎。這是背包問題的特殊性，雖然最后返回的是能裝的最多的重量旗扑，但是保存的卻是能否拼出某個重量蹦骑。（這應該是累和問題的特殊性，如果狀態(tài)是某列表的最大值肩豁，如copybooks脊串，那么這種解法直接失效了）

8.4
LinCode 563. Backpack V: 背包問題5，也是滾動數(shù)組就足夠維護狀態(tài)了清钥。new[j] = old[j] + old[j - nums[i-1]] 琼锋。
LinCode 562. Backpack IV: 滾動數(shù)組維護狀態(tài)，在5的基礎上祟昭，加入一個while循環(huán)缕坎，不停地減nums[i-1]，比如篡悟，f[7] = old[7] + old[7-3] + old[7 - 3 -3] ...谜叹。
LintCode 125. Backpack II: 額外的背包問題聯(lián)系，掌握套路過后搬葬，只是轉(zhuǎn)換方程有變化而已荷腊。
LintCode 440. Backpack III: python裝怪啊。
LintCode 799. Backpack VIII： 帶數(shù)量的金幣分配急凰，問題不大女仰，類似于IV，只不過是或連接抡锈。

8.5
516. Longest Palindromic Subsequence: 區(qū)間型DP疾忍，注意計算順序有套路，要按照序列長度計算床三。另外python過不了一罩，java能過。