目标和（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<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;  
    }  
    //把他们转成字符串才能作为哈希表的键  
 	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<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的背包？

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

• 如果不把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];