我們號之前寫過十幾篇動態(tài)規(guī)劃文章，可以說動態(tài)規(guī)劃技巧對于算法效率的提升非常可觀谁尸，一般來說都能把指數(shù)級和階乘級時間復(fù)雜度的算法優(yōu)化成 O(N^2)，堪稱算法界的二向箔纽甘，把各路魑魅魍魎統(tǒng)統(tǒng)打成二次元良蛮。
但是，動態(tài)規(guī)劃本身也是可以進行階段性優(yōu)化的悍赢，比如說我們常聽說的「狀態(tài)壓縮」技巧决瞳，就能夠把很多動態(tài)規(guī)劃解法的空間復(fù)雜度進一步降低，由 O(N^2) 降低到 O(N)左权，
能夠使用狀態(tài)壓縮技巧的動態(tài)規(guī)劃都是二維 dp 問題皮胡，你看它的狀態(tài)轉(zhuǎn)移方程，如果計算狀態(tài) dp[i][j] 需要的都是 dp[i][j] 相鄰的狀態(tài)赏迟，那么就可以使用狀態(tài)壓縮技巧胸囱，將二維的 dp 數(shù)組轉(zhuǎn)化成一維，將空間復(fù)雜度從 O(N^2) 降低到 O(N)瀑梗。
什么叫「和 dp[i][j] 相鄰的狀態(tài)」呢烹笔，比如前文 最長回文子序列 中，最終的代碼如下：
int longestPalindromeSubseq(string s) {
int n = s.size();
// dp 數(shù)組全部初始化為 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// 反著遍歷保證正確的狀態(tài)轉(zhuǎn)移
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 狀態(tài)轉(zhuǎn)移方程
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
// 整個 s 的最長回文子串長度
return dp[0][n - 1];
}
PS：我們本文不探討如何推狀態(tài)轉(zhuǎn)移方程抛丽，只探討對二維 DP 問題進行狀態(tài)壓縮的技巧谤职。技巧都是通用的，所以如果你沒看過前文亿鲜，不明白這段代碼的邏輯也無妨允蜈，完全不會阻礙你學(xué)會狀態(tài)壓縮。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)蒿柳，手把手刷 200 道力扣題目饶套，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新垒探。建議收藏妓蛮，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了圾叼。
你看我們對 dp[i][j] 的更新蛤克，其實只依賴于 dp[i+1][j-1], dp[i][j-1], dp[i+1][j] 這三個狀態(tài)：
這就叫和 dp[i][j] 相鄰捺癞，反正你計算 dp[i][j] 只需要這三個相鄰狀態(tài)，其實根本不需要那么大一個二維的 dp table 對不對构挤？狀態(tài)壓縮的核心思路就是髓介，將二維數(shù)組「投影」到一維數(shù)組：
思路很直觀，但是也有一個明顯的問題筋现，圖中 dp[i][j-1] 和 dp[i+1][j-1] 這兩個狀態(tài)處在同一列唐础，而一維數(shù)組中只能容下一個，那么當(dāng)我計算 dp[i][j] 時矾飞，他倆必然有一個會被另一個覆蓋掉一膨，怎么辦？
這就是狀態(tài)壓縮的難點凰慈，下面就來分析解決這個問題汞幢，還是拿「最長回文子序列」問題距離驼鹅，它的狀態(tài)轉(zhuǎn)移方程主要邏輯就是如下這段代碼：
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 狀態(tài)轉(zhuǎn)移方程
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
想把二維 dp 數(shù)組壓縮成一維微谓，一般來說是把第一個維度，也就是 i 這個維度去掉输钩，只剩下 j 這個維度豺型。壓縮后的一維 dp 數(shù)組就是之前二維 dp 數(shù)組的 dp[i][..] 那一行。
我們先將上述代碼進行改造买乃，直接無腦去掉 i 這個維度姻氨，把 dp 數(shù)組變成一維：
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 在這里，一維 dp 數(shù)組中的數(shù)是什么剪验？
if (s[i] == s[j])
dp[j] = dp[j - 1] + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
}
}
上述代碼的一維 dp 數(shù)組只能表示二維 dp 數(shù)組的一行 dp[i][..]肴焊，那我怎么才能得到 dp[i+1][j-1], dp[i][j-1], dp[i+1][j] 這幾個必要的的值，進行狀態(tài)轉(zhuǎn)移呢功戚？
在代碼中注釋的位置娶眷，將要進行狀態(tài)轉(zhuǎn)移，更新 dp[j]啸臀，那么我們要來思考兩個問題：
1届宠、在對 dp[j] 賦新值之前，dp[j] 對應(yīng)著二維 dp 數(shù)組中的什么位置乘粒？
2豌注、dp[j-1] 對應(yīng)著二維 dp 數(shù)組中的什么位置？
對于問題 1灯萍，在對 dp[j] 賦新值之前轧铁，dp[j] 的值就是外層 for 循環(huán)上一次迭代算出來的值，也就是對應(yīng)二維 dp 數(shù)組中 dp[i+1][j] 的位置旦棉。
對于問題 2属桦，dp[j-1] 的值就是內(nèi)層 for 循環(huán)上一次迭代算出來的值熊痴，也就是對應(yīng)二維 dp 數(shù)組中 dp[i][j-1] 的位置。
那么問題已經(jīng)解決了一大半了聂宾，只剩下二維 dp 數(shù)組中的 dp[i+1][j-1] 這個狀態(tài)我們不能直接從一維 dp 數(shù)組中得到：
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j])
// dp[i][j] = dp[i+1][j-1] + 2;
dp[j] = ?? + 2;
else
// dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
dp[j] = max(dp[j], dp[j - 1]);
}
}
因為 for 循環(huán)遍歷 i 和 j 的順序為從左向右果善，從下向上，所以可以發(fā)現(xiàn)系谐，在更新一維 dp 數(shù)組的時候巾陕，dp[i+1][j-1] 會被 dp[i][j-1] 覆蓋掉，圖中標(biāo)出了這四個位置被遍歷到的次序：
那么如果我們想得到 dp[i+1][j-1]纪他，就必須在它被覆蓋之前用一個臨時變量 temp 把它存起來鄙煤，并把這個變量的值保留到計算 dp[i][j] 的時候。為了達到這個目的茶袒，結(jié)合上圖梯刚，我們可以這樣寫代碼：
for (int i = n - 2; i >= 0; i--) {
// 存儲 dp[i+1][j-1] 的變量
int pre = 0;
for (int j = i + 1; j < n; j++) {
int temp = dp[j];
if (s[i] == s[j])
// dp[i][j] = dp[i+1][j-1] + 2;
dp[j] = pre + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
// 到下一輪循環(huán)，pre 就是 dp[i+1][j-1] 了
pre = temp;
}
}
別小看這段代碼薪寓，這是一維 dp 最精妙的地方亡资，會者不難，難者不會向叉。為了清晰起見锥腻，我用具體的數(shù)值來拆解這個邏輯：
假設(shè)現(xiàn)在 i = 5, j = 7 且 s[5] == s[7]，那么現(xiàn)在會進入下面這個邏輯對吧：
if (s[5] == s[7])
// dp[5][7] = dp[i+1][j-1] + 2;
dp[7] = pre + 2;
我問你這個 pre 變量是什么母谎？是內(nèi)層 for 循環(huán)上一次迭代的 temp 值瘦黑。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目奇唤，全部發(fā)布在 labuladong的算法小抄幸斥，持續(xù)更新。建議收藏咬扇，按照我的文章順序刷題甲葬，掌握各種算法套路后投再入題海就如魚得水了。
那我再問你內(nèi)層 for 循環(huán)上一次迭代的 temp 值是什么冗栗？是 dp[j-1] 也就是 dp[6]演顾，但這是外層 for 循環(huán)上一次迭代對應(yīng)的 dp[6]，也就是二維 dp 數(shù)組中的 dp[i+1][6] = dp[6][6]隅居。
也就是說钠至，pre 變量就是 dp[i+1][j-1] = dp[6][6]，也就是我們想要的結(jié)果胎源。
那么現(xiàn)在我們成功對狀態(tài)轉(zhuǎn)移方程進行了降維打擊棉钧，算是最硬的的骨頭啃掉了，但注意到我們還有 base case 要處理呀：
// dp 數(shù)組全部初始化為 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
dp[i][i] = 1;
如何把 base case 也打成一維呢涕蚤？很簡單宪卿，記住狀態(tài)壓縮就是投影的诵，我們把 base case 投影到一維看看：
二維 dp 數(shù)組中的 base case 全都落入了一維 dp 數(shù)組，不存在沖突和覆蓋佑钾，所以說我們直接這樣寫代碼就行了：
// 一維 dp 數(shù)組全部初始化為 1
vector<int> dp(n, 1);
至此西疤，我們把 base case 和狀態(tài)轉(zhuǎn)移方程都進行了降維，實際上已經(jīng)寫出完整代碼了：
int longestPalindromeSubseq(string s) {
int n = s.size();
// base case：一維 dp 數(shù)組全部初始化為 0
vector<int> dp(n, 1);
for (int i = n - 2; i >= 0; i--) {
int pre = 0;
for (int j = i + 1; j < n; j++) {
int temp = dp[j];
// 狀態(tài)轉(zhuǎn)移方程
if (s[i] == s[j])
dp[j] = pre + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
pre = temp;
}
}
return dp[n - 1];
}
本文就結(jié)束了休溶，不過狀態(tài)壓縮技巧再牛逼代赁，也是基于常規(guī)動態(tài)規(guī)劃思路之上的。
你也看到了兽掰，使用狀態(tài)壓縮技巧對二維 dp 數(shù)組進行降維打擊之后芭碍，解法代碼的可讀性變得非常差了，如果直接看這種解法孽尽，任何人都是一臉懵逼的窖壕。算法的優(yōu)化就是這么一個過程，先寫出可讀性很好的暴力遞歸算法杉女，然后嘗試運用動態(tài)規(guī)劃技巧優(yōu)化重疊子問題瞻讽，最后嘗試用狀態(tài)壓縮技巧優(yōu)化空間復(fù)雜度。
也就是說宠纯，你最起碼能夠熟練運用我們前文 動態(tài)規(guī)劃框架套路詳解 的套路找出狀態(tài)轉(zhuǎn)移方程卸夕，寫出一個正確的動態(tài)規(guī)劃解法层释，然后才有可能觀察狀態(tài)轉(zhuǎn)移的情況婆瓜，分析是否可能使用狀態(tài)壓縮技巧來優(yōu)化。
希望讀者能夠穩(wěn)扎穩(wěn)打贡羔，層層遞進廉白，對于這種比較極限的優(yōu)化，不做也罷乖寒。畢竟套路存于心猴蹂，走遍天下都不怕！
