DP動態規劃學習筆記

• 2019 年 11 月 9 日
• 筆記

作為考察範圍最廣，考察次數最多的算法，當然要開一篇博客來複習啦。

子曰：溫故而知新，可以為師矣

我複習DP時有一些自己對DP的理解，也就分享出來吧。

——正片開始——

動態規划算法，即Dynamic Programming(以下簡稱為DP)，是解決多階段決策過程最優化問題的高效數學方法。自從1999年IOI出了一道名為”數字三角形”的題後，DP題就在OI競賽中廣為流傳。而上面提到的”數字三角形”，現在就是DP的一道入門題。

遞推和DP的關係：

很多人會混淆遞推和DP，遞推只是DP的一種實現方式。我們提到的DP是一種高效的算法，實現方式主要是遞推和記憶化搜索，但是DP和遞推很像的一點就是，它們都是利用子問題來搞定原問題。

我舉一個例子，斐波那契數列，相信大家都不陌生。

我們知道Fib的遞推式：F(x) = F(x-1) + F(x-2)，可以通過第x-1項和第x-2項推出第x項。

如果我們從DP的角度來看Fib，我們可以把求第x項看成原問題，然後我們把求第x-1項和求第x-2項看成子問題，我們就把”求第x項”這個原問題劃分成了”求第x-1項”和”求第x-2項”兩個子問題，然後繼續劃分子問題並求解，最後利用所有的子問題得到原問題的解。

很多DP的入門博客都會仔細詳解DP的三個基本性質，解題步驟和使用DP的特徵。

不明白這些的，我從@mengmengdastyle的blog中摘取了這一段給你們看：

（2） 動態規劃包含三個重要的概念：
– 最優子結構
– 邊界
– 狀態轉移方程
（3）解題的一般步驟是：
1. 找出最優解的性質，刻畫其結構特徵和最優子結構特徵；
2. 遞歸地定義最優值，刻畫原問題解與子問題解間的關係；
3. 以自底向上的方式計算出各個子問題、原問題的最優值，並避免子問題的重複計算；
4. 根據計算最優值時得到的信息，構造最優解。
（4）使用動態規劃特徵：
1. 求一個問題的最優解
2. 大問題可以分解為子問題，子問題還有重疊的更小的子問題
3. 整體問題最優解取決於子問題的最優解（狀態轉移方程）
4. 從上往下分析問題，從下往上解決問題
5. 討論底層的邊界問題

以上。

本文注重思路和解題技巧，對於基本知識不多贅述。

我們先來分析一道題，通過這道題讓你明白DP是用來幹什麼的。

給你一個高度為x(1<=x<=2×10^5)的樓梯，每次可以向上走1級或者2級，問你走到頂一共有多少種走法。

輸入樣例：

10
輸出樣例：

89

我們來分析一下這道題，假如x=1，答案你可以很輕鬆的得到，等於1，如果x=2呢？答案是2，也很容易得到。

但是我們的x是可以很大的，我們不可能對於每個x都手算出結果存下來。

於是我們考慮分解問題，將原問題分解成若干子問題，然後對於每個子問題也分解下去。

“大事化小，小事化了。”

那我們怎麼分解這個問題呢？如果我們要求走3級的走法數，首先我們看看能否用走1級和走2級的方案數湊出走3級的方案數。於是，我們發現，確實可以。我們走3級的走法數就是走1級的走法數+走2級的走法數。

至此這個問題得解了：走x級的走法數=走x-1級的走法數+走x-2級的走法數。

這題就是求一個斐波那契數列，我們利用遞推得到答案。

介紹更困難的題目前，我打算講一講DP本身。

在OI競賽中，我們使用計算機計算答案。但是我們用計算機只能記錄下一些狀態，我們需要利用記錄下來的狀態去求解，於是我們要嘗試把問題定義成一個狀態。很多人在講DP的時候，說需要“遞歸”的定義狀態。對於這種說法，我們一般用兩個字來形容：扯淡。我們確實需要定義狀態，但是，每個問題都可以被定義成狀態，我們要做的首先就是思考怎麼去定義它，一般來說就是思考我們存什麼變量，算什麼變量，用這些變量怎麼得出解。

我們一般把問題劃分成不同階段，每個階段有不同狀態。但是，我們並不需要算出所有狀態存下來，我們每一步只需要存最優的答案就行了，這就是DP用來求最優解的原因。既然問題都是可以劃分成階段和狀態的，那麼，某一階段的最優解就一定可以通過之前階段的最優解得到。

但是，如果我們僅通過前一個階段的答案算不出當前階段的答案呢？如果我們需要前面所有階段的答案呢？

如果在問題的每個階段，一個狀態都可以轉移到下一個階段的多個狀態，那我們計算解的時間複雜度就是指數級別的，也就是說我們並不能用DP來解決這個問題。這種，前面的決策會影響後面的情況，就被稱為有後效性。

還記得DP的三個要素之一嗎？無後效性。

記得搜索的入門題嗎？01迷宮。

如果我們要找到從起點到終點的最短路徑，我們可以只保存當前階段的狀態嗎？顯然不行。想想我們當時做的時候保存的狀態？{x,y,step}，以及一個vis數組。由於題目要求我們求的路徑最短，我們必須知道之前走過的所有位置。

即使我們當前在同一個位置，我們之前走的路線不同，也是會影響到我們後面選擇走的路徑的，因為我們不會走已經標記vis過的格子了。

所以我們必須保存每個階段經歷過的所有狀態才能得到下一個階段的解。

這就是有後效性的問題的一個例子。

如果我們需要記錄之前所有的狀態，我們的複雜度就是指數級的，但是DP呢？

我們並不需要記錄之前的所有狀態，我們當前的決策並不受之前狀態的組合的影響了，就可以多項式時間內出答案了。

引用一段@X丶dalao的blog：

每個階段只有一個狀態->遞推；
每個階段的最優狀態都是由上一個階段的最優狀態得到的->貪心；
每個階段的最優狀態是由之前所有階段的狀態的組合得到的->搜索；
每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到而不管之前這個狀態是如何得到的->動態規劃。

每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到
這個性質叫做最優子結構；

而不管之前這個狀態是如何得到的
這個性質叫做無後效性。

好了，現在我們講題。

網上各種什麼，讓你徹底學懂DP啊，特別的DP入門教程啊，其實都不如自己多寫點DP題來的實在…

下面我將從幾道例題開始，從易到難慢慢打開DP的大門。

1. 石子合併：
有n堆石子排成一列，每堆石子有一個重量w[i], 每次合併可以合併相鄰的兩堆石子，一次合併的代價為兩堆石子的重量和w[i]+w[i+1]。問安排怎樣的合併順序，能夠使得總合併代價達到最小。

首先我們來劃分階段，我們有一坨長度為n的石子堆，我們每次合併後，石子堆的數量都會減少，那我們就從這裡切入。

直觀地想，我們可能會這樣劃分階段：

我們要合併石子，肯定就要找一個地方，把它兩邊的石子合併起來。              

設f[x]表示合併了x次的最小總代價。立刻就能發現不對…我們選定不同的地方來合併，每次的答案時不同的，也就是說f[x]的值不定，這時肯定是得不到最優解的。有人可能會有疑問，f[x]不是定義成了最小定義的代價了嗎？

那你回去仔細看看上面說的關於狀態定義的內容。

所以我們需要重新定義狀態，這裡給出一種劃分方法，我們用f[i,j]表示合併區間左端點為i，右端點為j的這段區間合併成一堆石子的最優值。

為什麼這麼定義呢？這就涉及到一類問題：區間DP。

對於區間DP，我們利用區間長度作為階段，用左右端點表示狀態。這種定義方法可以解決大部分的區間DP問題了，但是遇到一些難題，我們還需要加維度來解決。

我們上面提到過，要合併兩堆石子，我們就要循環一個分界點，我們定義一個分界點k，枚舉這個分界點找最優解。這個過程我們稱之為——決策！

然後我們利用決策轉移狀態（用子問題求解出原問題）：

下面這個式子就是我們常聽到的“狀態轉移方程”：

f[i,j] = f[i][k] + f[k+1][j] + cost(i,j)，其中cost(i,j)表示合併兩堆石子的代價。

然後我們思考一下狀態的可選範圍，i表示左端點，j表示右端點。

i: 1~n-len+1，j：i+len-1，這樣我們就保證了既不超出邊界，又能保證我們的階段是區間長度len。

階段就是len：2~n

這種做法時間複雜度是O(n^4)，我們發現沒法簡化定義了，於是我們O(n^3)預處理出cost(i,j)，再O(n^3)DP得出答案。

偽代碼大概是這樣的：

for(i,1,n)      for(j,i,n)          for(k,i,j)              cost(i,j)+=w[k]  for(len,2,n)      for(i,1,n-len+1)          j=i+len-1          for(k,i,j)              f[i][j]=min(f[i][j],f[i][k]+f[k+1][r]+cost(i,j))

如果還是不太理解的可以仔細去看看這道題的題解，博主這一篇博客只打算講思路，不仔細講例題。接下來我們看這樣一道題：沒有上司的舞會

題目描述已經說了，它們的關係像一棵有根樹，那我們就在樹上DP。這種依賴樹形結構的DP我們也把它們劃分為一類：

樹形DP。

這時候可能就有人想問了，既然也是一類DP，它的階段劃分是不是也和區間DP一樣，有套路呢？

沒錯。樹形DP依賴樹形結構，那麼我們很容易想到樹的性質，父親和子節點的關係一一對應，我們可以通過子節點的信息計算父節點的信息。也就是，這類題已經幫我們劃分好階段了，節點從深到淺的順序就是我們的階段，我們用一個從上到下的遍歷來進行DP，對於每個子節點x先往下遞歸在它的每個子節點進行DP，再在回溯的時候從子節點向節點x轉移狀態。這樣我們需要做的就是定義狀態了。定義狀態也很容易，我們一般選擇每個節點的編號x作為狀態的第一維，再根據不同題目的需求加維進行DP。

回到這道題目上來，我們根據上面的內容，先定義第一維為節點編號，然後我們會發現，一個節點的信息值只與它參不參加舞會有關係，於是我們定義f[x][0/1]為它參加/不參加時的值。

題目也明確說了，如果一個人的直接上司參加了舞會他就不會參加，那我們就可以輕鬆的得到狀態轉移方程：
f[x][0]+=max(f[y][0],f[y][1])，f[x][1]+=f[y][0]，y∈son(x)

然後遞歸求解就好了。

寫到這裡我發現我實在是講不完所有的DP類型了，於是我們後面會跳過幾種DP分為下一篇來談。

放到下一篇講的DP（狀壓DP，計數DP，數位DP，概率與期望DP，所有優化方法）

那麼我們就回過來講DP中一類很特殊的問題：背包問題

什麼是背包問題？我們先從基礎的0/1背包開始，逐步分析背包問題的模型。

給你n個物品，其中，第i個物品的體積為wi，價值為vi。再給你一個容積為m的背包，現在讓你在不超過容積的範圍內選出一些物品裝入背包讓價值儘可能大。

首先我們可能會想到用貪心來解決這道題目，但是貪心很顯然是錯誤的。

我們貪心的策略很顯然是每次選擇“性價比”最高的物品，也就是wi/vi最大的物品。

但是，對於0/1背包問題，貪心選擇之所以不能得到最優解是因為：

它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。

明白這一點後，我們考慮用DP求解。

如何劃分階段呢？很顯然，我們依次考慮是否選擇每件物品，然後我們還需要知道現在背包用了多少容積。

那我們就設f[i][j]為前i件物品中裝了j體積的物品的最大價值。

這裡我們用另外一種思路來想轉移方程式，我們不分解這個問題，我們直接考慮狀態怎麼推進。

我們前i件物品中裝j體積的最大價值很顯然是由前i-1件物品裝了某體積的物品，再考慮選不選擇當前這件物品轉移過來的。

那我們很容易就可以得到如下的轉移方程：

f[i][j]=max(

　　f[i-1][j],//選這件物品

　　if(j>=wi)

　　　　f[i-1][j-wi]+v[i] //不選這件物品

　　else

　　　　f[i-1][j] //選不了這件物品

)

階段：前i件物品(i∈[1,n])

狀態：當前的容積(j∈[m,0])

這樣我們的空間複雜度是O(n^2)的，考慮優化空間。

我們發現第一位是可以省略的（我們按順序依次考慮每個物品即可）。

於是…就變成了這樣：

for(int i=1;i<=n;i++)    　　for(int j=m;j>=w[i];j--)    　　　　f[j]=max(f[j],f[j-w[i]]+v[i]);

 我們每個物品只能放一次，而我們的f[j]要通過f[j-w[i]]計算得到。

如果，我們使用正序循環，從w[i]到m，那麼我們可能出現這種情況：

f[j]被f[j-wi]+vi更新過，當我們j增加到j+w[i]時，f[j+w[i]]又有可能被f[j]+vi更新，而同時它們都處於階段i，也就是說，我們在一個階段內的兩個狀態間發生了轉移，相當於第i個物品被使用了多次（如果後面又更新了），不符合0/1背包的要求。

所以我們要倒序循環，這樣我們的j會一直縮小，不會出現“同階段間轉移”的情況，所以，問題至此得解。

接下來我們要講完全背包，思考這樣一個問題：

給你n種物品，每種物品有無數個，其中，第i種物品的體積為wi，價值為vi。再給你一個容積為m的背包，現在讓你在不超過容積的範圍內選出一些物品裝入背包讓價值儘可能大。

注意它和0/1背包問題的區別，0/1背包每種物品只有一個，而完全背包有無數個。

細心的讀者可能發現了，我們上面說，當我們正序循環時，相當於一個物品被使用了多次，符合完全背包的要求…那我們只要正序循環，是不是就？

還是太想當然了啊，當然沒錯。

然後我們講講多重背包吧，還是一個類似的問題：

給你n種物品，每種物品有ci個，其中，第i種物品的體積為wi，價值為vi。再給你一個容積為m的背包，現在讓你在不超過容積的範圍內選出一些物品裝入背包讓價值儘可能大。

每種物品從無數個變成了ci個，也就是有了限制，怎麼做呢？

水題啊！我們把每種物品看成ci個不同的物品不就好了？然後跑一遍0/1背包，問題不久得解了咩？

天真啊，這樣的時間複雜度可是 $O(m*sumlimits_{i=1}^nc_i)$ 的啊（第一次用Latex有點不習慣）

那咋整啊？我們又延伸出了：單調隊列優化DP。

DP的種類真是數不勝數…不過優化DP是下一篇的內容，這裡不再敘述。

不想用單調隊列優化DP來解決多重背包的話，我們可以二進制拆分多重背包。

我們大概是這樣一個拆分思路，把每一種物品拆成log個不同物品。

大概是這樣拆：

int cnt=0;  for(int i=1;i<=n;i++){      int a,b,c;      cin>>a>>b>>c;      for(int j=1;j<=c;j<<=1){          v[++cnt]=j*a,w[cnt]=j*b;          c-=j;      }      if(c)//剩下拆不掉的部分，直接當新物品          v[++cnt]=c*a,w[cnt]=c*b;  }

思路還是很簡單的，但是很巧妙。拆完就是一個0/1背包了，很水。

我佛了…還有個分組背包沒講…這篇博客都寫了2天了QuQ，DP真難講。

限於篇幅和時間，樹上的背包問題我留到下一篇的開頭…

給出分組背包的模型：

給你n組物品，每組物品有ci個，其中，第i組第j個物品的體積為wi,j，價值為vi,j。再給你一個容積為m的背包，現在讓你在不超過容積的範圍內每組至多選一個物品裝入背包讓價值儘可能大。

分組背包是一類樹形DP的很重要的組成Part，所以熟練掌握它還是很重要滴。

這個問題我們怎麼做呢？

考慮用線性DP解決（…霧），我們要滿足“每組至多選擇一個物品”的要求，就可以利用“階段”線性增長的特性，把物品組數作為階段，只要選了一個第i組的物品，就轉移狀態到下一個階段就好了^-^。然後仿照0/1背包的做法，設f[i][j]表示從前i組中選出總體積為j的物品放入了背包，物品的最大價值和。

f[i,j]=max{

　　f[i-1,j],//不選第i組的物品喵

　　max{f[i-1,j-wik]+vik},(1<=k<=ci)//選第i組的某個物品k喵->是做決策噠

}

上面那東西不是我敲的…但是她不讓我刪掉

我們還是可以省略掉第一維，別問，問就是這是背包問題。為什麼呢？因為我們可以用j的倒序循環來控制階段i的狀態只能由階段i-1轉移得到。

至此問題得解，給出代碼：

for(int i=1;i<=n;i++)      for(int j=m;j>=0;j--)          for(int k=1;k<=c[i];k++)              if(j>=w[i][k])                  f[j]=max(f[j],f[j-w[i][k]+v[i][k]);

總結一下，這篇博客我們接觸並初步學習了動態規划算法，並對DP的本質有了一定的了解，明白了設計DP算法求解問題的一般思路。沒錯，設計DP算法，DP算法迷人的地方就在於，對於每道DP題，都需要自己去設計一個合理且高效的DP算法去解決問題，這也是DP難的地方。除此之外，我們還學習了幾種常見的DP模型，加深了對“階段，狀態，決策”的理解。DP題要難可以難上天，要簡單可以一眼秒，但是本質上看它們都是考察同一個東西：腦子。DP題其實不難個鬼，只要你理解了DP的基本實現方法，稍加思考，把問題轉化一下，就很容易想到如何用DP去求解答案。

對於這種依靠思維的題目，其實不用寫很多題。雖然刷題是必不可缺的，但是對於寫過的每道DP題，都確保自己理解了思路，明白了為什麼這樣設計DP，就可以總結出一套自己應對DP題的方法和技巧，每個人寫DP題的方法都是不盡相同的。希望通過這篇博客，能讓你喜歡上動態規划算法。

更深層次難度更高的DP，我會在下一篇博客里討論。不過就連這篇博客我都寫了整整兩天，下一篇可能我要寫挺久了。除非我夠肝。

你們的點贊就是我最大的動力（其實我就是想自己整理整理…），感謝你們的支持。