目标和(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];