# 动态规划和回溯算法到底谁是谁爹
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是什么关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，时否可以互相转化呢？
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划，真可谓群魔乱舞：
# 回溯思路
其实这题用回溯思路非常简单，任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法，我们套用之前说过的回溯算法框架:
function backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
关键就是搞清楚什么是「选择」，而对于这道题，「选择」不是明摆着的吗？ 对于每个数字 nums[i] ，我们可以选择给一个正号 ＋ 或者一个负号 - ， 然后利用回溯模板琼剧出所有可能的结果，数一数到底有几种组合能够凑出 target 不就行了。
伪代码如下：
function backtrack(nums, i):
if i === len(nums):
if 达到 target:
result += 1
return
for op in { +1, -1 }:
选择 op * nums[i]
// 穷举 nums[i + 1] 的选择
backtrack(nums, i + 1)
撤销选择
具体实现：
function findTargetSumWays(nums: number[], target: number): number {
if(!nums.length) return 0
let result = 0
function backtrack(nums: number[], index: number, rest: number): void {
if(index === nums.length) {
if(rest === 0) result++
return
}
// 选择 - 号
rest += nums[index]
backtrack(nums, index + 1, rest)
// 撤销选择
rest -= nums[index]
// 选择 + 号
rest -= nums[index]
backtrack(nums, index + 1, rest)
// 撤销选择
rest += nums[index]
}
backtrack(nums, 0, target)
return result
}
可能有人会问，为什么选择 + 号的时候是 - ，选择 - 号的时候是 + 呢？
注意看 rest 这个形参的定义，表示剩余值，因此刚好是相反的。
以上算法的时间复杂度是指数级别 O(2 ^ N) ，原因是每一个元素都会做出 2 次选择，其中 N 表示数组的长度。
# 消除重叠子问题
动态规划之所以比暴力算法快，就是因为动态规划消除了重叠子问题。
如何发现重叠子问题？看是否可能出现重复的「状态」。对于递归函数来说，函数参数中会变的参数就是「状态」，对于 backtrack 函数来说，会变得参数为 index 和 rest。
我们先尝试抽象出递归框架：
void backtrack(int index, int rest) {
backtrack(index + 1, rest - nums[index])
backtrack(index + 1, rest + nums[index])
}
举个简单的例子，如果 nums[i] 等于 0 会发生什么？
void backtrack(int index, int rest) {
backtrack(index + 1, rest)
backtrack(index + 1, rest)
}
至此，我们可以发现出现了两个完全相同的「状态」的递归函数， 这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。
因此，状态 index 和 和 rest 是可以用备忘录技巧来进行优化的。
function findTargetSumWays(nums: number, target: number): number {
if(!nums.length) return 0
const hashmap = new Map<string, number>()
function dp(nums: number, index: number, rest: number): number {
if(index === nums.length) {
if(!rest) return 1
return 0
}
let key = `${index}-${rest}`
if(hashmap.has(key)) return hashmap.get(key)
const result = dp(nums, index + 1, rest + nums[index]) + dp(nums, index + 1, rest - nums[index])
hashmap.set(key, result)
return result
}
return dp(nums, 0, target)
}
这个解法通过备忘录消除了很多重叠子问题，在效率上有一定的提升，但是这就结束了？
# 动态规划
其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑......
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么它们和 target 存在如下关系：
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，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？
类似的子集划分问题我们前文 经典背包问题：子集划分 讲过，现在实现这么一个函数：
/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {}
然后，可以这样调用这个函数：
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);
}
好的，变成背包问题的标准形式：
有一个背包，容量为 sum****，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]****（注意 1 <= i <= N****），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？
现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：
第一步要明确两点，「状态」和「选择」。
对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；dp[..][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。
我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
PS：注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。
由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
然后，根据状态转移方程写出动态规划算法：
/* 计算 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]) {
// 两种选择的结果之和
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];
}
然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维 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--) {
// 状态转移方程
if (j >= nums[i-1]) {
dp[j] = dp[j] + dp[j-nums[i-1]];
} else {
dp[j] = dp[j];
}
}
}
return dp[sum];
}
对照二维 dp****，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：
因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。
那么，我们就要做到：在计算新的 dp[j] 的时候，****dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。
如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。
现在，这道题算是彻底解决了。
总结一下，回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造，从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出状态压缩，还得反向遍历。
现在我都搞不清楚自己是来干嘛的了。嗯，这也许就是动态规划的魅力吧。