前言

計算機歸根結底只會做一件事：窮舉。
所有的算法都是在讓計算機【如何聰明地窮舉】而已，動態規劃也是如此。

---

動態規劃的精髓

什么叫“狀態”

每一個 DP 子問題，都可以用一組變量來唯一標識。把這組變量稱為一個 “狀態”，用 $dp[狀態]$來表示該子問題的最優解（或方案數、合法性等）。

舉個例子，我在實驗室坐著敲代碼，小王在圖書館站著處對象、小明在水房倒立洗頭…

• 這里的（我，實驗室，坐著，敲代碼），（小王，圖書館，站著，處對象），（小明，水房，倒立，洗頭）就是三組狀態，可以用一個四維的數組來表示，$dp[i][j][k][l]$就表示$i$這個人，在$j$這個地方，以$k$這樣的動作，干$l$這件事時的某種性質。

狀態轉移也好理解，舉個例子：在游戲中，有幾個技能，其中一個技能叫“轉換”，可以讓人物在跑、走、跳之間來回切換，消耗$a$點體力。其中一個狀態轉移就是消耗$a$點體力將走切換成跑，如果用$dp$數組表示放$i$次技能，達到當前狀態消耗的體力的最小值，也就是$dp[i][跑]=min(dp[i][跑],dp[i?1][走]+a)$ ，這個式子就叫做狀態轉移方程。

動態規劃的概念

前置知識：遞歸、遞推

動態規劃（Dynamic programming，簡稱DP） 是一種通過將原問題分解成幾個彼此之間有關聯的、相對簡單的子問題來求解復雜問題的算法。

動態規劃把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解。

動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。

動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

動態規劃的三要素

動態規劃有很經典的三要素：重疊子問題、最優子結構、狀態轉移方程。

首先，雖然動態規劃的核心思想就是窮舉求最值或方案數，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，需要你熟練掌握遞歸思維，只有列出正確的 「狀態轉移方程」 ，才能正確地窮舉。而且，你需要判斷算法問題是否具備 「最優子結構」，是否能夠通過子問題的最值得到原問題的最值。另外，動態規劃問題存在 「重疊子問題」，如果暴力窮舉的話效率會很低，所以需要你使用 「記憶化」 來優化窮舉過程，避免不必要的計算。

動態規劃的框架

// 自頂向下遞歸的動態規劃
int dp(狀態1, 狀態2, ...){for(int 選擇 : 所有的選擇){# 此時的狀態已經因為做了選擇而改變res = 求最值(res, dp(狀態1, 狀態2, ...));}return res;
}// 自底向上遞推的動態規劃
# 初始化 base case
dp[0][0][...] = base case;
# 進行狀態轉移
for(狀態1 : 狀態1的所有取值){for(狀態2 : 狀態2的所有取值){for(狀態3 : 狀態3的所有取值){dp[狀態1][狀態2][...] = 求最值(選擇1, 選擇2, ...);}}
}

無后效性

tips:動態規劃的題要求你的轉移無后效性，那什么叫無后效性呢

無后效性，即前面的選擇不會影響后面的游戲規則。

尋路算法中，不會因為前面走了 B 路線而對后面路線產生影響。斐波那契數列因為第 N 項與前面的項是確定關聯，沒有選擇一說，所以也不存在后效性問題。

什么場景存在后效性呢？比如你的人生是否能通過動態規劃求最優解？其實是不行的，因為你今天的選擇可能影響未來人生軌跡，比如你選擇了計算機這個專業，會直接影響到你大學四年學的課程、接觸到的人，四年的大學生活因此就完全變了，所以根本無法與選擇了土木工程的你進行比較。

有同學可能覺得這樣局限是不是很大？其實不然，無后效性的問題仍然很多，比如背包放哪件物品、當前走哪條路線、用了哪些零錢，都不會影響整個背包大小、整張地圖的地形、以及你最重要付款的金額…

dfs -> 記憶化搜索 -> dp

821. 跳臺階

暴力寫法

#include <iostream>
#define endl '\n'
using namespace std;int f(int n){if(n == 0 || n == 1) return 1;return f(n - 1) + f(n - 2);
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;cout << f(n) << endl;return 0;
}

可以看出，暴力做法有很多遞歸的分支都是重復的，也就是有很多重復的子問題。這些重復的子問題在下一次遇到時如果每次都重新計算一遍就會很浪費時間，所以可以用一個數組記錄一下，下次再遇到直接查表即可，這也就是記憶化搜索。

記憶化搜索寫法

#include <iostream>
#define endl '\n'
using namespace std;int dp[16];int f(int n){if(dp[n]) return dp[n];if(n == 0 || n == 1) return 1;return dp[n] = f(n - 1) + f(n - 2);
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;cout << f(n) << endl;return 0;
}

記憶化搜索優化了什么？怎么轉化成dp？

• 暴力：每個子問題都考慮一次。
• 記憶化搜索：對于相同的子問題，只考慮一次。

那是不是可以理解為：dp就是在暴力的基礎上，把所有效果相同的狀態都放在了一個集合里？暴力是單一狀態和單一狀態之間某種屬性的轉移，而dp是集合和集合之間某種屬性的轉移？

比如這道題，$dp[i]$表示的集合就是：所有從第$0$級臺階走到第$i$級臺階的合法方案。
屬性就是：集合中元素的數量。

所以綜上，$dp[i]$就表示：所有從第$0$級臺階走到第$i$級臺階的方案數。

dp寫法

#include <iostream>
#define endl '\n'
using namespace std;int dp[16];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;dp[0] = 1, dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[n] << endl;return 0;
}

dp其實也是圖論

首先先說結論：

動態規劃 (DP) 很多時候其實就是在一個狀態圖（嚴格來說是一個有向無環圖，DAG）上做一次「拓撲遍歷＋松弛」的過程。

在動態規劃（DP）中，我們把“子問題”看作圖中的“節點”，把“從一個子問題推導到另一個子問題”的依賴關系看作有向邊，那么所有這些狀態和邊就構成了一張有向無環圖（DAG）。而對這張DAG做一次拓撲排序——恰好保證了：當我們要計算某個狀態的最優值（或計數、最小／最大代價……）時，它依賴的所有前驅狀態都已經計算完畢。

最大值、最小值，是不是相當于是求最長路、最短路，求方案數是不是就相當于是沿著拓撲序列累加？

狀態DAG是怎樣的？

• 節點（state）
  每一個 DP 子問題 $S$ 都對應 DAG 中的一個節點。
  例如，經典“爬樓梯”問題中，讓 $dp[i]$ 表示到達第 $i$ 級臺階的方案數，
  那么節點就是 $0,1,2,\dots ,n$。

• 有向邊（依賴）
  如果計算 $dp[v]$ 需要用到 $dp[u]$，就在 DAG 中加一條從 $u$ 指向 $v$ 的邊。
  爬樓梯里，$dp[i]$ 可由 $dp[i?1]$ 和 $dp[i?2]$ 推出，就有兩條邊：
  $(i?1)\to i,(i?2)\to i$。

• 無環
  DP 的定義通常是“從小問題推向大問題”，不存在循環依賴，圖上必然是無環的。

dp問題的初始化

dp問題的初始化經常不是很好理解，但如果你站在拓撲排序、最短路問題的角度來看，就會相對好理解一些。

回憶一下你學過的所有的最算路問題，代碼是不是都有這樣的兩部分初始化：

memset(dist, 0x3f, sizeof dist); // 所有點dist初始化成正無窮
dist[s] = 0; // 源點dist初始化成0

dp問題的初始化其實也是這樣的，分成兩部分：

• 對所有的點進行初始化：比如求最小值，memset(dp, 0x3f, sizeof dp)。
  對于這種初始化，一般如果是求最小值，就初始化成一個極大值；如果求最大值，就初始化成一個極小值；如果是求數量，就初始化成0。
• 對“源點”進行初始化：單源最短路的問題源點只有一個，就給源點初始化成0，而拓撲排序就相當于是一個多源的最短路，源點就是所有入度為0的點，在dp中也就是那些最基本的狀態（base case），這種初始化只需將所有的base case都按dp狀態表示的含義，初始化成對應的數即可。比如數字三角形問題中：最頂端的點不能由任何點走過來，于是直接將其初始化成對應的值，或者你可以看做最頂端的點可以由上面下標為0的點走過來，所以也可以將所有下標為0的點初始化成0。

很多問題對“源點”的初始化經常會初始化下標為$0$的位置，像下面這樣：

	for(int i = 1; i <= n; i++){dp[i][0] = i;}for(int i = 1; i <= m; i++){dp[0][i] = i;}

怎么確定base case呢？一般來說，如果你的dp遍歷是for(int i = a; ...)，那base case就很有可能是你的i = a的前一個狀態（前驅結點），多維也是同樣的道理。

簡單來講，一個dp問題，你循環遍歷的所有點都是狀態DAG上入度不為0的點，你單拎出來初始化的點都是狀態DAG入度為0的點。

dp問題的答案

和初始化相同，初始化是初始化所有的“起點”（入度為0的點），那答案就是所有的“終點”（出度為0的點），如果“終點”有很多個，就要定義一個結果變量，對于求最值，需要遍歷一下所有出度為0的狀態取個最值；對于求方案數，需要逐個判斷、累加一下。

分析dp題的步驟

• 做dp題，首先就要把dp數組寫出來，首先要想：dp數組要開幾維：一般來說，如果不優化狀態表示的話，有幾個狀態dp數組就要開幾維。
• 然后，搞明白你dp數組的含義，也就是搞明白集合的表示和集合的屬性。集合的屬性常見的可能有最大值（max）、最小值（min）、數量（cnt）…
• 最后，寫出狀態轉移方程，對應的過程就是將問題分成若干子問題的過程，也就是集合的劃分。
• 然后，想怎么初始化，求最大值就初始化成極小值、求最小值就初始化成極大值、求數量就初始化成0…
• 然后，寫代碼：定義dp數組、初始化、for循環枚舉所有的狀態，輸出結果。

具體各個過程都是什么意思：看下面的幾個線性dp經典模型。

數字三角形

898. 數字三角形

狀態表示

因為有行和列，所以狀態要開二維:$dp[i][j]$

• 集合：所有從$a[1][1]$走到$a[i][j]$的路線
• 屬性：（路線經過數字和的）最大值（max）

綜上：$dp[i][j]$:所有從$a[1][1]$走到$a[i][j]$的路線的數字和的最大值

狀態計算

集合劃分：將這個集合劃分成幾個不同的集合，就要找一個不同的步驟。

可以看出，走到$a[i][j]$的這最后一步可以是從$a[i?1][j]$走過來的，也可以是從$a[i?1][j?1]$走過來的，所以可以從最后一步來劃分這個集合，前一個集合是$dp[i?1][j]$，后一個集合是$dp[i?1][j?1]$。

顯然：$dp[i][j]=max(dp[i?1][j?1]+a[i][j],dp[i?1][j]+a[i][j])$

初始化

要求最大值，并且有負數，先將所有位置都初始化成負無窮。

因為和要從0開始加，而不是負無窮，所以要將所有的$dp[0][j]$和$dp[i][0]$都初始化成0。

但上面這樣比較麻煩，因為所有路線都是從起點開始走的，所以直接將起點初始化成$a[1][1]$，循環從$2$開始遍歷即可。

AC代碼

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 505;int a[N][N];
int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){cin >> a[i][j];}}memset(dp, -0x3f, sizeof dp);dp[1][1] = a[1][1];for(int i = 2; i <= n; i++){for(int j = 1; j <= i; j++){dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];}}int res = -0x3f3f3f3f;for(int i = 1; i <= n; i++) res = max(res, dp[n][i]);cout << res << endl;return 0;
}

最長上升子序列（LIS）

895. 最長上升子序列

狀態表示

序列只有一維，dp數組也開一維就夠了: $dp[i]$

• 集合：所有以$a[i]$結尾的上升子序列
• 屬性：（長度的）最大值

綜上：$dp[i]$：所有以$a[i]$結尾的上升子序列的長度的最大值。

狀態計算

集合劃分：將這個集合劃分成幾個不同的集合，就要找一個不同的步驟。

因為最后一步都是相同的，都是將$a[i]$加到序列中，無法劃分，所以看倒數第二步：也就是加$a[i]$前這個上升子序列是以什么元素結尾的。想一下，如果$a[i]$能加到一個以$a[j]$結尾的上升子序列的后面，是不是一定要滿足$a[i]>a[j]$ ?

所以這個集合就可以劃分成：所有滿足$a[i]>a[j]$( $0$ $\le$ $j$ $<$$i$)的以$a[j]$結尾的上升子序列接上一個$a[i]$。

狀態轉移方程就出來了：$dp[i]=max(dp[i],dp[j]+1)(a[j]<a[i])$。

初始化

求最大值，上升子序列最短都是1，都初始化成1即可。

AC代碼

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int a[N];
int dp[N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];dp[i] = 1;}for(int i = 1; i <= n; i++){for(int j = 1; j < i; j++){if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);}}int res = 1; for(int i = 1; i <= n; i++) res = max(res, dp[i]);cout << res << endl;return 0;
}

優化

很顯然，用dp求LIS是$O(n^2)$的，如果$n$比較大會超時，但可以基于貪心+二分、單調棧、單調隊列等多種方式進行優化到$O(nlogn)$、$O(n)$，因為這是dp專題，就不細講了。

最長公共子序列（LCS）

897. 最長公共子序列

狀態表示

有兩個序列，一個序列開一維，兩個序列就開二維：$dp[i][j]$

• 集合：所有$a$的前$i$個元素和$b$的前$j$個元素的公共子序列
• 屬性：（長度的）最大值

綜上：$dp[i][j]$表示所有$a$的前$i$個元素和$b$的前$j$個元素的公共子序列的長度的最大值。

狀態計算

集合劃分：將這個集合劃分成幾個不同的集合，就要找一個不同的步驟。

看最后一步，$a$的前$i$個元素的子序列里，是不是有的帶$a[i]$，有的不帶$a[i]$? $b$的前$j$個元素的子序列里，是不是有的帶$b[j]$，有的不帶$b[j]$?那二者的公共子序列是不是也如此？

所以可以以$a[i]$和$b[j]$是否包含在公共子序列中為依據進行劃分。

然后想這幾個集合的狀態怎么表示，可以分成下面四種情況：

• 情況1：$a[i]$,$b[j]$ 均存在于 最長公共子序列中 (前提$a[i]==b[j]$)
• 情況2：$a[i]$ 在，$b[j]$ 不在 （無前提）
• 情況3：$a[i]$, $b[j]$ 均不在 （無前提）
• 情況4：$a[i]$不在，$b[j]$在 （無前提）

初步想一下，是不是可以表示成下面這樣：

• 情況1：暫用$dp[i?1][j?1]+1$表示
• 情況2：暫用$dp[i][j?1]$表示
• 情況3：暫用$dp[i?1][j?1]$表示
• 情況4：暫用$dp[i?1][j]$表示

但這樣表示真的對嗎？事實上是不嚴謹的，舉個例子：$dp[i][j?1]$的集合表示的是所有$a$的前$i$個元素和$b$的前$j?1$個元素的公共子序列，$b$的前$j$個元素一定是不包含$b[j]$的，但 $a$的前$i$個元素是不是可能包含$a[i]$，也可能不包含$a[i]$? $dp[i?1][j]$也是一樣的道理

所以實際上 $dp[i?1][j]$表示的是情況2+情況3，$dp[i][j?1]$表示的是情況3+情況4 。

因為這個模型dp的屬性是求最大值，集合之間有交集不會影響答案，保證不漏就行(就好像你要求10個數的最大值，你知道前7個數的最大值和后7個數的最大值，只需要這兩個集合取max就可以了），所以狀態計算直接取$dp[i?1][j?1]+1$、$dp[i][j?1]$、$dp[i?1][j]$三者的最大值就可以了。

狀態轉移方程也就出來了：
$dp[i][j]=max(dp[i?1][j],dp[i][j?1])$
$dp[i][j]=max(dp[i][j],dp[i?1][j?1]+1)(a[i]==b[j])$

也可以換種方式理解：對于字符串$a$和$b$中的每個字符都有且只有兩種狀態：在公共子序列中和不在公共子序列中。那是不是可以從后往前遍歷每一個字符：如果$a[i]==b[j]$，這個字符就一定在公共子序列中，也就是情況1，而如果$a[i]\ne a[j]$，這兩個字符就至少有一個不在公共子序列中，需要丟棄一個，也就是情況2、3、4。

初始化

求最大值，公共子序列最小都是0，都初始化成0即可。

AC代碼

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;cin >> n >> m;string a, b;cin >> a >> b;a = " " + a, b = " " + b;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= m; i++) cin >> b[i];for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);}}cout << dp[n][m] << endl;return 0;
}

最短編輯距離

902. 最短編輯距離

狀態表示

有兩個字符串，開兩維，$dp[i][j]$

• 集合：所有讓$a$的前$i$個字符和$b$的前$j$個字符變得相同的操作方式
• 屬性：（操作次數的）最小值

綜上：$dp[i][j]$表示所有讓$a$的前$i$個字符和$b$的前$j$個字符變得相同的操作次數的最小值。

狀態計算

集合劃分：將這個集合劃分成幾個不同的集合，就要找一個不同的步驟。

還是看最后一步，最后一步肯定是改變$a$的一個字符后 $a[1$ ~ $i]$ 變得和$b[1$ ~ $j]$相同，而改變字符有三種方式：增加、刪除和替換。

首先要弄清楚一點，插入操作實際上是在末尾添加一個字符，刪除操作一定是刪掉最后一個字符。

為什么呢？拿刪除舉例子，首先，如果你某一步的操作是刪除中間的字符，刪除位置后面的整個序列都會改變，這就不滿足無后效性。其次，如果某一步刪除操作刪除的是中間的字符，那么這個操作在之前一定可以通過刪除最后的字符來實現，也就相當于是之前漏刪了，后面來補，并且末尾的$b[j]$也沒動到，這一定不是最優的子結構，并且如果你某一步的操作是刪除中間的字符，每次刪除的位置都難以決定，這也就不是重疊的子問題。

而如果你每次都刪最后的字符，每次操作都是相同的，也不會影響后面的決策，并且是最優的。

任何最優路徑的最后一步，絕不會故意留一段未對上的后綴不管，再去中間做事然后回來補尾巴。

• 如果最后一步是增加一個字符：為了讓$a[1$ ~ $i]$ 變得和$b[1$ ~ $j]$相同，最后加的字符就一定是$b[j]$，而$a[1$ ~ $i]+b[j]$和$b[1$ ~ $j]$相同，也就說明$a[1$ ~ $i]+b[j]$和$b[1$ ~ $j?1]+b[j]$相同，也就說明原來的$a[1$ ~ $i]$ 和$b[1$ ~ $j?1]$是相同的，也就是$dp[i][j?1]+1$

• 如果最后一步是刪除某個字符：刪掉的字符一定是$a[i]$，而如果刪$a[i]$后$a[1$ ~ $i]$ 變得和$b[1$ ~ $j]$相同，就說明$a[1$ ~ $i]?a[i]$ 和$b[1$ ~ $j]$相同，也就是$a[1$ ~ $i?1]+a[i]?a[i]$ 和$b[1$ ~ $j]$相同，也就是$dp[i?1][j]+1$

• 如果最后一步是改變某個字符：
  如果$a[i]\ne b[j]$，就一定要把$a[i]$改成$b[j]$，如果改之后相同了，就說明$a[1$ ~ $i?1]+b[j]$ 和$b[1$ ~ $j]$相同，也就是$a[1$ ~ $i?1]+b[j]$ 和$b[1$ ~ $j?1]+b[j]$相同，也就是$a[1$ ~ $i?1]$ 和$b[1$ ~ $j?1]$相同，也就是$dp[i?1][j?1]+1$

  如果$a[i]=b[j]$，最后的字符就不用管，只需將$a[1$ ~ $i?1]$ 和$b[1$ ~ $j?1]$變得相同，也就是$dp[i?1][j?1]$。

然后可以得出狀態轉移方程：
$dp[i][j]=min(dp[i?1][j]+1,dp[i][j?1]+1)$
$dp[i][j]=min(dp[i][j],dp[i?1][j?1]+(a[i]\ne b[j]))$

初始化

求最小值，最大的編輯距離也就是全改一遍的情況，狀態轉移的起點也就是空串的時候，這時候恰巧是全改，只需給所有的$dp[i][0]、dp[0][i]$都初始化成$i$即可。

AC代碼

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;string a, b;cin >> n >> a >> m >> b;a = " " + a;b = " " + b;for(int i = 1; i <= n; i++){dp[i][0] = i;}for(int i = 1; i <= m; i++){dp[0][i] = i;}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; // 增和刪if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); // 不用改else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); // 改}}cout << dp[n][m] << endl;return 0;
}