目标和（LeetCode 494 难度：中等）

下面用目标和来对比动态规划和回溯

回溯思路

任何框架的核心思想都是穷举，回溯算法是一个暴力穷举，前面写过算法框架：

result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择


关键搞清楚什么是选择，而对于这道题，选择不是明摆着呢嘛？对于一个数字num[i]，可以 选择给一个 正号 + 号 或者 一个负号 -号，然后利用回溯穷举：

class Solution {
int res=0;
int rest=0;
public int findTargetSumWays(int[] nums, int target) {
helper(nums,0,target);
return res;
}
private void helper(int[] nums,int i, int target){
if(i==nums.length){
if(rest==target){
res++;
}
return ;
}
//给个正常符号
rest=rest+nums[i];
helper(nums,i+1,target);
//回溯
rest=rest-nums[i];
//给个 正常符号的相反符号
rest=rest+-nums[i];
helper(nums,i+1,target);
//回溯
rest=rest+nums[i];
}
}


消除重叠子问题

动态规划比回溯算法快，因为动态规划 消除了重叠子问题

如何发现重叠子问题呢？看看是否出现过重复的状态。对于递归来说，函数参数中会变的参数就是状态，对于 helper()来说，会变的参数是 i和 target

先抽象递归过程

void backtrack(int i,int rest){
backtrack(i+1,rest-nums[i]);
backtrack(i+1,rest+nums[i]);
}


举个简单的例子 ，如果nums[i]==0，会发生什么？

void backtrack(int i,int rest){
backtrack(i+1,rest);
backtrack(i+1,rest);
}


你看这样就出现了两个状态完全相同的递归函数，无疑这样样的递归计算就是重复的。这就是重叠子问题，而且，只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题

因此，状态（i，rest）是可以用备忘录技巧去优化的：

int findTargetSumWays(int nums[],int target){
if(nums.length==0)return 0;
return dp(nums,0,target);_
}
//备忘录
HashMap memo=new HashMap<>();
int dp(int nums[],int i,int rest){
//base case
if(i==nums.length){
if(rest==0){
return 1;
}
return 0;
}
//把他们转成字符串才能作为哈希表的键
String key=i+","+rest;
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;
}


可以把状态转化为字符串作为哈希表的键，这是一个常用的技巧。

动态规划

其实这个问题可以转为一个子集切分问题，而子集切分问题又是一个背包问题。动态规划就是让人捉摸不透。

首先，如果把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 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的背包？

第三步，根据选择，思考状态转移的逻辑

• 如果不把nums[i]装入子集，或者说不把第 i 个物品装入背包，那么，恰好装满背包的方法就取决于上一次的状态dp[i-1][j]，继承之前的结果


• 如果把nums[i]装入子集，或者说把第 i 个物品装入背包，那么要看前** i-1** 个物品有几种方法可以装满 j-nums[i-1]的重量就行了，所以就取决于dp[i-1] [j-nums[i-1]]；

注意：这里说的 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]];


然后根据状态转移方程推出动态规划算法：

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]<0){
//背包容量不足，继承之前的结果
dp[i][j]=dp[i-1][j];
}else {
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][sum];