前兩篇我總結(jié)了鏈表和二分查找題目的一些套路，這篇文章來講講動態(tài)規(guī)劃。動態(tài)規(guī)劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉(zhuǎn)移方程的題目，大部分動態(tài)規(guī)劃都不太會做。加上后來ACM更為令人頭禿的動態(tài)規(guī)劃，很多題解看了之后，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數(shù)優(yōu)化，一度懷疑自己的智商。以前一直覺得動態(tài)規(guī)劃是給大佬準備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是后來慢慢的，我再做LC的時候，發(fā)現(xiàn)很多DP的題目我自己慢慢能夠推出轉(zhuǎn)移方程了，而且似乎也沒那么難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是后者，但是同時我也發(fā)現(xiàn)，動態(tài)規(guī)劃其實是有套路的，我以前方法不對，總結(jié)太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態(tài)規(guī)劃畢竟要滿足：

• 階段性
• 無后效性
• 子問題重疊性

因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現(xiàn)有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經(jīng)典DP模型，就需要通過大量的做題和總結(jié)，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結(jié)加深理解和融會貫通進而完成質(zhì)的提升。

動態(tài)規(guī)劃是求解一個最優(yōu)化問題，而最核心的思想就是：

• 分而治之
• 想辦法記錄下中間的計算結(jié)果避免重復計算

解一道DP題目，先問自己幾個問題：

• 我需要最少哪些數(shù)據(jù)，然后經(jīng)過一些比較就能得出最終結(jié)果？
• 這些數(shù)據(jù)的求解是否可以用同樣的方法分而治之？
• 過程中的運算結(jié)果如何保存復用？

當然以上內(nèi)容看起來比較抽象，雖然它深刻地揭露了動態(tài)規(guī)劃的本質(zhì)，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結(jié)出幾個經(jīng)典模型，剩下的都是些變種+優(yōu)化而已。

一般來說，動態(tài)規(guī)劃可以分成4個大類:

• 線性DP
• 區(qū)間DP
• 樹型DP
• 背包

線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是經(jīng)典模型。

最長上升序列

最長上升序列是一個非常經(jīng)典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎(chǔ)上進一步優(yōu)化而已。最長上升序列最基礎(chǔ)的轉(zhuǎn)移方程就是f[i] = max{f[j]}+1 (a[i] > a[j]),f[i]表示一定要以a[i]結(jié)尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的f[j]同時滿足a[j]<a[i]。因此是N^2的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關(guān)題目需要進一步優(yōu)化，也就是有名的單調(diào)隊列優(yōu)化，能夠把復雜度優(yōu)化到nlogn。

說單調(diào)隊列優(yōu)化之前必須明白一個貪心策略。因為要求的是最長上升序列，那么很顯然長度為k的上升序列的最大值（最后一個數(shù)）越小越好，這樣后面的數(shù)才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最后一個數(shù)能達到的最小值，那么對于后續(xù)每個數(shù)t，它要么能放到某個長度為y的序列之后，組成長度為y+1的上升序列，要么放到某個長度為x的序列后面，把長度為x+1的序列的最大值替換成t。同時我們可以發(fā)現(xiàn)，如果x<y，那么長度為x序列的最后一個數(shù)一定比長度為y的序列最后一個數(shù)小。因此這個上升序列我們可以用一個數(shù)組來維護（所謂的單調(diào)隊列），數(shù)組下標就代表序列長度。opt[i]=t表示長度為i的上升序列最后一個數(shù)最小是t。那么當我們在面對后續(xù)某個數(shù)x時，可以對單調(diào)隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關(guān)題目比如：

• 300. 最長上升子序列，裸題，但是要擊敗100%的話，需要單調(diào)隊列優(yōu)化。
• 354. 俄羅斯套娃信封問題，這道題還是hard。之前的最長上升序列是一維的，這道題是二維的上升序列，滿足Ax<Bx且Ay<By，才可以構(gòu)成上升序列。那么我們可以根據(jù)x進行排序，然后對y求解最長上升子序列。但是這里有個地方需要注意，因為x必須要嚴格升序，排序之后可能存在(1,1) (1,2) (1,3) (2,4)這樣的序列，如果對y進行求解上升序列，會得到4，但是實際應該只是2。為了避免這個問題，在排序時，如果x相等，則y按照降序排列，就可以規(guī)避這個問題。
• 合唱隊形，這道題是要求一個形如1 3 4 7 9 8 6 5 2這樣的子序列。先上升再下降，最后求最長的長度。其實解決辦法也很簡單，先從左到右求出所有的最長上升序列asc[i]，再從右到左求出所有的最長上升序列reverseAcc[i]，最大值就是max(asc[i]+reverseAcc[i])。對算法要能夠靈活運用。

但是你可以發(fā)現(xiàn)，其實這個題型其實變種很有限，吃透了也就那么回事。所以一定要總結(jié)。

LCS 最長公共子序列

最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種“模型”其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎(chǔ)上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數(shù)組的最長公共子序列，最直觀地做法就是：設(shè)f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:

• f[i][j] = f[i-1][j-1] + 1 ...... S[i]==T[j]
• f[i][j] = max(f[i-1][j], f[i][j-1]) ...... S[i]≠T[j]

這個轉(zhuǎn)移方程也非常好理解，時間復雜度是N^2，空間復雜度也是N^2。不過仔細觀察你可以發(fā)現(xiàn)，當我們計算第i行時只與i-1和i行有關(guān)。因此我們可以利用01滾動來優(yōu)化空間復雜度為2N。
相關(guān)題目：

• 1143. Longest Common Subsequence：這道題就是裸的LCS
• 583. Delete Operation for Two Strings：兩個字符串要刪除成一樣的，所以先找出最長公共序列，然后剩下的都刪了。
• 718. Maximum Length of Repeated Subarray：這道題其實本質(zhì)上不是LCS，它是尋找最長子數(shù)組，而不是子序列（子數(shù)組要求連續(xù)）。需要搞清它們的區(qū)別。找子數(shù)組就更簡單了，因為必須連續(xù)，所以f[i][j] = f[i-1][j-1]+1 : 0 ? S[i]==T[j]。通過倒序枚舉能夠把空間優(yōu)化為O(N)。
• 1092. Shortest Common Supersequence：這道題是hard，實際上也不算很hard。其實就是找到最長公共子序列，然后，對于A字符串，把除了LCS以外的字符插入到對應的位置；對于B字符串也做同樣的操作。這道題大家需要掌握一個新姿勢，就是除了求最長公共子序列有多長，還要會打印最長公共子序列（follow up：打印所有可能的最長公共子序列）。同時，要把剩余的字符插入到對應的位置其實可以想辦法把原字符串按照LCS切分成k+1段，比如對于字符串A abcxdef，其lcs為bde，那么我們可以把原字符串切成4段 a bcx d ef，同樣對于B字符串，也能切成4段，然后對應插入構(gòu)成新字符串即可，需要注意的就是，從第1段開始，第一個字符是lcs字符，所以只插一次。相關(guān)代碼可以參考我的實現(xiàn)

線性遞推

線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉(zhuǎn)移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結(jié)的題型：

股票買賣問題

• 121. Best Time to Buy and Sell Stock：當前的最大收益只依賴于之前的最小買入價格。因此只需要一個變量保存截至目前的最低價即可，每次更新最大收益。
• 122. Best Time to Buy and Sell Stock II：由于可以進行多次交易，那么只要明天比今天價格高就有得賺，就可以進行交易。不需要去找波峰波谷，因為day2-day1+day3-day2 == day3-day1。當然，這里掌握怎么找波峰波谷的代碼很重要，后面題目的優(yōu)化會用到
• 123. Best Time to Buy and Sell Stock III：要求最多交易兩次，而第二次交易必須建立在完成第一次交易的基礎(chǔ)之上，因此對于每天來說，存在4種狀態(tài)：第一次買、第一次賣、第二次買、第二次賣）。我們可以用f[i][0..=4]來表示這些狀態(tài)：
  • 對于第一次買，f[i][1] = max(f[i-1][1], -prices[i])
  • 第一次賣，f[i][2] = max(f[i-1][2], f[i-1][1]+prices[i])
  • 第二次買，f[i][3] = max(f[i-1][3], f[i-1][2]-prices[i])
  • 第二次賣，f[i][4] = max(f[i-1][4], f[i-1][3]+prices[i])

最終結(jié)果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發(fā)現(xiàn)，由于各個狀態(tài)只和前一維有關(guān)，且只能由固定的一個狀態(tài)轉(zhuǎn)移過來，因此我們可以省掉一維，只用4個變量來存儲：

 first_buy = max( first_buy,  -p[i] )
 first_sell = max(first_sell,  first_buy + p[i] )
 second_buy = max(second_buy,  -p[i] )
 second_sell = max(second_sell, second_buy + p[i] )

• 188. Best Time to Buy and Sell Stock IV：這道題更進一步，要求最多不超過k次交易。這道題有幾個小優(yōu)化點：
  • 由于一次交易需要2天，n天最后進行n/2次交易，因此如果k>=n/2，那么這道題就簡化為不限交易次數(shù)的122. Best Time to Buy and Sell Stock II
  • 對于 1 3 4 6 7 7 8這樣的上升序列，交易3次和一頭一尾交易一次的結(jié)果是一樣的，因此可以只保留1 8,；同理，對于8 7 7 5 4 4 2 1這樣的連續(xù)下降序列，由于價格連續(xù)下降，中間進行交易肯定虧，因此在最低點再買入肯定比高點買入劃算，可以只保留8 1（保留8是因為它是前一個的上升序列的高點）。這種方式能夠在絕大部分情況大大減少數(shù)據(jù)規(guī)模，配合第一個小優(yōu)化，很容易把題目簡化成不限交易次數(shù)的122. Best Time to Buy and Sell Stock II

剩下的，同123題類似，由于最多進行k次交易，那么一天就有2k個狀態(tài)：第1次買/賣……第k次買/賣，結(jié)合123題的優(yōu)化，我們只需要2k個變量就能存儲這些狀態(tài)。因此設(shè)f[i×2]為第i次買入的最優(yōu)值，f[i×2+1]為第i次賣出的最優(yōu)值：

for j in 0..prices.len() {
  let price = prices[j];
  f[0] = max(f[0], -price);
  f[1] = max(f[1], f[0]+price);
  for i in 1..k { // 這里還有個優(yōu)化，因為只枚舉到第j天，因此最多能進行j/2+1次交易，這里可以只枚舉到min(k, j/2+1)
    f[i*2] = max(f[i*2], f[i*2-1]-p[j]);
    f[i*2+1] = max(f[i*2+1], f[i*2]+p[j]);
  }
}

打家劫舍

• 198. House Robber：其實就是在一個數(shù)組中取數(shù)，數(shù)與數(shù)之間至少隔一個，問最大能取到多少。由于第i個數(shù)能不能取依賴于前一個數(shù)是否被取過，因此用f[i]表示取第i個數(shù)能得到的最大值，用g[i]表示不取第i個數(shù)能得到的最大值。f[i] = g[i-1]+a[i], g[i] = max(f[i-1], g[i-1])。然后發(fā)現(xiàn)，由于只和前一項有關(guān)，因此可以只用兩個變量來保存。f = g+a[i]，g = max(g, f)。
• 213. House Robber II：同樣的規(guī)則，只是把數(shù)組變成了環(huán)，意味收尾兩個數(shù)也相鄰了。怎么處理環(huán)這個約束呢？其實就是，只要取了第一個就不能取最后一個，或者取了最后一個就不能取第一個。要解決這個問題一個簡單的辦法就是，直接把最后一個元素刪了，然后進行一次DP，得到結(jié)果A。然后把最后一個元素加回去再把第一個元素刪了，進行一次DP，得到結(jié)果B。這樣能夠保證不會同時取到收尾元素。最后比較AB，取較大值即可。
• 337. House Robber III：這道題把數(shù)組變成了二叉樹，要求父節(jié)點和子節(jié)點不能同時取。雖然是在樹上DP，但其實也很簡單。設(shè)計一個get(root) -> (i32, i32)方法，此方法返回兩個值，一個是取根節(jié)點所能達到的最大值，一個是不取根節(jié)點能達到的最大值。偽代碼如下：

fn get(root) -> (i32, i32) {
  if root.is_none() {
    return (0,0);
  }
  let (lch_with_root, lch_without_root) = get(root.lch);
  let (rch_with_root, rch_without_root) = get(root.rch);
  (
    root.val+lch_without_root+rch_without_root,
    max(lch_with_root, lch_without_root) + max(rch_with_root, rch_without_root),
  )
}

粉刷房子

• 256. 粉刷房子：因為相鄰房子不能顏色一樣，因此當前房子刷什么顏色還依賴于它前一個房子刷什么顏色。因此用f[i][j]表示前i個房子，且第i個房子刷顏色j能得到的最小花費。那么f[i][j] = min(f[i-1][k])+cost[i][j]，其中k!=j。也就是從前i-1個房子，且第i-1個房子刷顏色k，轉(zhuǎn)移過來。由于相鄰顏色不能一樣，因此不能從f[i-1][j]轉(zhuǎn)移，即k!=j。由于f[i]只和f[i-1]有關(guān)，因此可以用01滾動來優(yōu)化一維空間。而且對于這道題，只有三種顏色，實際上完全可以用6個變量pre_red, pre_blue, pre_green, red, blue, green來表示。
• 265. 粉刷房子 II：同上一題，這道題顏色不固定，因此使用f[2][0..k]來分別表示k種顏色的狀態(tài)。f[i][j] = min(f[1-i][k])+cost[i][j]

小結(jié)

以上都是對一些常見的線性DP的一些小結(jié)，實際上線性DP還有一個重要的題型就是背包。關(guān)于背包，有很多相關(guān)的講解，我這里就不多說了，推薦大家看看背包九講。下一章依然是DP專題，我講總結(jié)一些區(qū)間DP的題型。大部分區(qū)間DP都是hard級的，對于希望提高自己水平的人來說，需要投入更多精力去理解。