我們前文經(jīng)常說回溯算法和遞歸算法有點類似，有的問題如果實在想不出狀態(tài)轉(zhuǎn)移方程，嘗試用回溯算法暴力解決也是一個聰明的策略，總比寫不出來解法強。
那么，回溯算法和動態(tài)規(guī)劃到底是啥關(guān)系？它倆都涉及遞歸，算法模板看起來還挺像的，都涉及做「選擇」，真的酷似父與子。
那么，它倆具體有啥區(qū)別呢？回溯算法和動態(tài)規(guī)劃之間，是否可能互相轉(zhuǎn)化呢？
今天就用力扣第 494 題「目標(biāo)和」來詳細(xì)對比一下回溯算法和動態(tài)規(guī)劃，真可謂群魔亂舞：
注意，給出的例子 nums 全是 1，但實際上可以是任意正整數(shù)哦。
其實我第一眼看到這個題目，花了兩分鐘就寫出了一個回溯解法。
任何算法的核心都是窮舉，回溯算法就是一個暴力窮舉算法，前文 回溯算法解題框架 就寫了回溯算法框架：
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇
關(guān)鍵就是搞清楚什么是「選擇」，而對于這道題，「選擇」不是明擺著的嗎？
對于每個數(shù)字 nums[i]，我們可以選擇給一個正號 + 或者一個負(fù)號 -，然后利用回溯模板窮舉出來所有可能的結(jié)果，數(shù)一數(shù)到底有幾種組合能夠湊出 target 不就行了嘛？
偽碼思路如下：
def backtrack(nums, i):
if i == len(nums):
if 達(dá)到 target:
result += 1
return
for op in { +1, -1 }:
選擇 op * nums[i]
# 窮舉 nums[i + 1] 的選擇
backtrack(nums, i + 1)
撤銷選擇
如果看過我們之前的幾篇回溯算法文章，這個代碼可以說是比較簡單的了：
int result = 0;
/* 主函數(shù) */
int findTargetSumWays(int[] nums, int target) {
if (nums.length == 0) return 0;
backtrack(nums, 0, target);
return result;
}
/* 回溯算法模板 */
void backtrack(int[] nums, int i, int rest) {
// base case
if (i == nums.length) {
if (rest == 0) {
// 說明恰好湊出 target
result++;
}
return;
}
// 給 nums[i] 選擇 - 號
rest += nums[i];
// 窮舉 nums[i + 1]
backtrack(nums, i + 1, rest);
// 撤銷選擇
rest -= nums[i];
// 給 nums[i] 選擇 + 號
rest -= nums[i];
// 窮舉 nums[i + 1]
backtrack(nums, i + 1, rest);
// 撤銷選擇
rest += nums[i];
}
有的讀者可能問，選擇 - 的時候，為什么是 rest += nums[i]，選擇 + 的時候，為什么是 rest -= nums[i] 呢，是不是寫反了？
不是的，「如何湊出 target」和「如何把 target 減到 0」其實是一樣的。我們這里選擇后者，因為前者必須給 backtrack 函數(shù)多加一個參數(shù)，我覺得不美觀：
void backtrack(int[] nums, int i, int sum, int target) {
// base case
if (i == nums.length) {
if (sum == target) {
result++;
}
return;
}
// ...
}
因此，如果我們給 nums[i] 選擇 + 號，就要讓 rest - nums[i]，反之亦然。
以上回溯算法可以解決這個問題，時間復(fù)雜度為 O(2^N)，N 為 nums 的大小。這個復(fù)雜度怎么算的？回憶前文 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維，發(fā)現(xiàn)這個回溯算法就是個二叉樹的遍歷問題：
void backtrack(int[] nums, int i, int rest) {
if (i == nums.length) {
return;
}
backtrack(nums, i + 1, rest - nums[i]);
backtrack(nums, i + 1, rest + nums[i]);
}
樹的高度就是 nums 的長度嘛，所以說時間復(fù)雜度就是這棵二叉樹的節(jié)點數(shù)，為 O(2^N)，其實是非常低效的。
那么，這個問題如何用動態(tài)規(guī)劃思想進(jìn)行優(yōu)化呢？
動態(tài)規(guī)劃之所以比暴力算法快，是因為動態(tài)規(guī)劃技巧消除了重疊子問題。
如何發(fā)現(xiàn)重疊子問題？看是否可能出現(xiàn)重復(fù)的「狀態(tài)」。對于遞歸函數(shù)來說，函數(shù)參數(shù)中會變的參數(shù)就是「狀態(tài)」，對于 backtrack 函數(shù)來說，會變的參數(shù)為 i 和 rest。
前文 動態(tài)規(guī)劃之編輯距離 說了一種一眼看出重疊子問題的方法，先抽象出遞歸框架：
void backtrack(int i, int rest) {
backtrack(i + 1, rest - nums[i]);
backtrack(i + 1, rest + nums[i]);
}
舉個簡單的例子，如果 nums[i] = 0，會發(fā)生什么？
void backtrack(int i, int rest) {
backtrack(i + 1, rest);
backtrack(i + 1, rest);
}
你看，這樣就出現(xiàn)了兩個「狀態(tài)」完全相同的遞歸函數(shù)，無疑這樣的遞歸計算就是重復(fù)的。這就是重疊子問題，而且只要我們能夠找到一個重疊子問題，那一定還存在很多的重疊子問題。
因此，狀態(tài) (i, rest) 是可以用備忘錄技巧進(jìn)行優(yōu)化的：
int findTargetSumWays(int[] nums, int target) {
if (nums.length == 0) return 0;
return dp(nums, nums.length - 1, target);
}
// 備忘錄
HashMap<String, Integer> memo = new HashMap<>();
int dp(int[] nums, int i, int rest) {
// base case
if (i == nums.length) {
if (rest == 0) return 1;
return 0;
}
// 把它倆轉(zhuǎn)成字符串才能作為哈希表的鍵
String key = i + ',' + rest;
// 避免重復(fù)計算
if (memo.containsKey(key)) {
return memo.get(key);
}
// 還是窮舉
int result = dp(nums, i + 1, rest - nums[i]) + dp(nums, i + 1, rest + nums[i]);
// 記入備忘錄
memo.put(key, result);
return result;
}
以前我們都是用 Python 的元組配合哈希表 dict 來做備忘錄的，其他語言沒有元組，可以用把「狀態(tài)」轉(zhuǎn)化為字符串作為哈希表的鍵，這是一個常用的小技巧。
這個解法通過備忘錄消除了很多重疊子問題，效率有一定的提升，但是這就結(jié)束了嗎？
事情沒有這么簡單，先來算一算，消除重疊子問題之后，算法的時間復(fù)雜度是多少？其實最壞情況下依然是 O(2^N)。
為什么呢？因為我們只不過恰好發(fā)現(xiàn)了重疊子問題，順手用備忘錄技巧給優(yōu)化了，但是底層思路沒有變，依然是暴力窮舉的回溯算法，依然在遍歷一棵二叉樹。這只能叫對回溯算法進(jìn)行了「剪枝」，提升了算法在某些情況下的效率，但算不上質(zhì)的飛躍。
其實，這個問題可以轉(zhuǎn)化為一個子集劃分問題，而子集劃分問題又是一個典型的背包問題。動態(tài)規(guī)劃總是這么玄學(xué)，讓人摸不著頭腦……
首先，如果我們把 nums 劃分成兩個子集 A 和 B，分別代表分配 + 的數(shù)和分配 - 的數(shù)，那么他們和 target 存在如下關(guān)系：
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)
綜上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原問題轉(zhuǎn)化成：nums 中存在幾個子集 A，使得 A 中元素的和為 (target + sum(nums)) / 2？
類似的子集劃分問題我們前文 經(jīng)典背包問題：子集劃分 講過，現(xiàn)在實現(xiàn)這么一個函數(shù)：
/* 計算 nums 中有幾個子集的和為 sum */
int subsets(int[] nums, int sum) {}
然后，可以這樣調(diào)用這個函數(shù)：
int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int n : nums) sum += n;
// 這兩種情況，不可能存在合法的子集劃分
if (sum < target || (sum + target) % 2 == 1) {
return 0;
}
return subsets(nums, (sum + target) / 2);
}
好的，變成背包問題的標(biāo)準(zhǔn)形式：
有一個背包，容量為 sum，現(xiàn)在給你 N 個物品，第 i 個物品的重量為 nums[i - 1]（注意 1 <= i <= N），每個物品只有一個，請問你有幾種不同的方法能夠恰好裝滿這個背包？
現(xiàn)在，這就是一個正宗的動態(tài)規(guī)劃問題了，下面按照我們一直強調(diào)的動態(tài)規(guī)劃套路走流程：
第一步要明確兩點，「狀態(tài)」和「選擇」。
對于背包問題，這個都是一樣的，狀態(tài)就是「背包的容量」和「可選擇的物品」，選擇就是「裝進(jìn)背包」或者「不裝進(jìn)背包」。
第二步要明確 dp 數(shù)組的定義。
按照背包問題的套路，可以給出如下定義：
dp[i][j] = x 表示，若只在前 i 個物品中選擇，若當(dāng)前背包的容量為 j，則最多有 x 種方法可以恰好裝滿背包。
翻譯成我們探討的子集問題就是，若只在 nums 的前 i 個元素中選擇，若目標(biāo)和為 j，則最多有 x 種方法劃分子集。
根據(jù)這個定義，顯然 dp[0][..] = 0，因為沒有物品的話，根本沒辦法裝背包；dp[..][0] = 1，因為如果背包的最大載重為 0，「什么都不裝」就是唯一的一種裝法。
我們所求的答案就是 dp[N][sum]，即使用所有 N 個物品，有幾種方法可以裝滿容量為 sum 的背包。
第三步，根據(jù)「選擇」，思考狀態(tài)轉(zhuǎn)移的邏輯。
回想剛才的 dp 數(shù)組含義，可以根據(jù)「選擇」對 dp[i][j] 得到以下狀態(tài)轉(zhuǎn)移：
如果不把 nums[i] 算入子集，或者說你不把這第 i 個物品裝入背包，那么恰好裝滿背包的方法數(shù)就取決于上一個狀態(tài) dp[i-1][j]，繼承之前的結(jié)果。
如果把 nums[i] 算入子集，或者說你把這第 i 個物品裝入了背包，那么只要看前 i - 1 個物品有幾種方法可以裝滿 j - nums[i-1] 的重量就行了，所以取決于狀態(tài) dp[i-1][j-nums[i-1]]。
PS：注意我們說的 i 是從 1 開始算的，而數(shù)組 nums 的索引時從 0 開始算的，所以 nums[i-1] 代表的是第 i 個物品的重量，j - nums[i-1] 就是背包裝入物品 i 之后還剩下的容量。
由于 dp[i][j] 為裝滿背包的總方法數(shù)，所以應(yīng)該以上兩種選擇的結(jié)果求和，得到狀態(tài)轉(zhuǎn)移方程：
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
然后，根據(jù)狀態(tài)轉(zhuǎn)移方程寫出動態(tài)規(guī)劃算法：
/* 計算 nums 中有幾個子集的和為 sum */
int subsets(int[] nums, int sum) {
int n = nums.length;
int[][] dp = new int[n + 1][sum + 1];
// base case
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
if (j >= nums[i-1]) {
// 兩種選擇的結(jié)果之和
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
} else {
// 背包的空間不足，只能選擇不裝物品 i
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][sum];
}
然后，發(fā)現(xiàn)這個 dp[i][j] 只和前一行 dp[i-1][..] 有關(guān)，那么肯定可以優(yōu)化成一維 dp：
/* 計算 nums 中有幾個子集的和為 sum */
int subsets(int[] nums, int sum) {
int n = nums.length;
int[] dp = new int[sum + 1];
// base case
dp[0] = 1;
for (int i = 1; i <= n; i++) {
// j 要從后往前遍歷
for (int j = sum; j >= 0; j--) {
// 狀態(tài)轉(zhuǎn)移方程
if (j >= nums[i-1]) {
dp[j] = dp[j] + dp[j-nums[i-1]];
} else {
dp[j] = dp[j];
}
}
}
return dp[sum];
}
對照二維 dp，只要把 dp 數(shù)組的第一個維度全都去掉就行了，唯一的區(qū)別就是這里的 j 要從后往前遍歷，原因如下：
因為二維壓縮到一維的根本原理是，dp[j] 和 dp[j-nums[i-1]] 還沒被新結(jié)果覆蓋的時候，相當(dāng)于二維 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。
那么，我們就要做到：在計算新的 dp[j] 的時候，dp[j] 和 dp[j-nums[i-1]] 還是上一輪外層 for 循環(huán)的結(jié)果。
如果你從前往后遍歷一維 dp 數(shù)組，dp[j] 顯然是沒問題的，但是 dp[j-nums[i-1]] 已經(jīng)不是上一輪外層 for 循環(huán)的結(jié)果了，這里就會使用錯誤的狀態(tài)，當(dāng)然得不到正確的答案。
現(xiàn)在，這道題算是徹底解決了。
總結(jié)一下，回溯算法雖好，但是復(fù)雜度高，即便消除一些冗余計算，也只是「剪枝」，沒有本質(zhì)的改進(jìn)。而動態(tài)規(guī)劃就比較玄學(xué)了，經(jīng)過各種改造，從一個加減法問題變成子集問題，又變成背包問題，經(jīng)過各種套路寫出解法，又搞出狀態(tài)壓縮，還得反向遍歷。
現(xiàn)在搞得我都忘了自己是來干嘛的了。嗯，這也許就是動態(tài)規(guī)劃的魅力吧。
-----
不過，送書活動還是不能忘。
從本月開始，為了回饋讀者們一直以來的支持，以后 labuladong 每月底都會組織一波送書活動。
聯(lián)系客服
