AlgoPressAppearance
0494-目标和
https://leetcode.cn/problems/target-sum
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
思路
背包问题
- 定义 dp[i,j] 表示从 0-i 中选出一些数，组成为j的最多种方法
- 状态转移方程 dp[i,j] = dp[i-1, j-nums[i]] + dp[i-1,j+nums[i]]
- 初始化 dp[0,j] 当 j = nums[0] 时， dp[0,j] = 1
参考代码
csharp
public class Solution {
public int FindTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
int[,] dp = new int[nums.Length,sum+1];
//设置初始值，表示
dp[0,nums[0]] = 1;
//状态转移
for(int i=0; i<nums.Length; i++){
for(int j=0; j<=sum; j++){
if(j>=nums[i]){
dp[i,j] += dp[i-1,j-nums[i]];
}
if(j+nums[i] <= sum){
dp[i,j] += dp[i-1,j+nums[i]];
}
}
}
return dp[nums.Length-1,target];
}
}
参考代码2：考虑负数区间的情况
注意dp数组循环的时候， j 从 -sum 然后到 sum ，并且计算 j+sum的值
csharp
public class Solution{
public int FindTargetSumWays(int[] nums, int target){
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
int range = sum*2+1;
int[,] dp = new int[nums.Length, range];
//设置初始值
//Console.WriteLine("range={0},sum={1}",range,sum);
dp[0,sum+nums[0]] += 1;
dp[0,sum-nums[0]] += 1; //如果nums[0] == 0 继续累积
//状态转移
for(int i=1; i<nums.Length; i++){
for(int j=-sum;j<=sum;j++){
if(j+sum >= nums[i]){
dp[i,j+sum] += dp[i-1,j+sum-nums[i]];
}
if(j+sum+nums[i] < range){
dp[i,j+sum] += dp[i-1,j+sum+nums[i]];
}
}
}
//返回结果
if(target+sum < range && target+sum >=0){
return dp[nums.Length-1,target+sum];
}
else{
return 0;
}
}
}
思路2：转换为01背包：思路巧妙
https://leetcode.cn/problems/target-sum/solution/by-mountain-ocean-v4g1/
目标和 target 总和是 sum, 加号组成的和是 x, x = (sum+target)/2 问题转化为，在nums中选择n个数，和组成x的方法数
参考代码
csharp
public class Solution{
public int FindTargetSumWays(int[] nums, int target){
int sum = 0;
for(int i=0; i<nums.Length; i++){
sum+=nums[i];
}
if(Math.Abs(target) > sum){
return 0;
}
if( (sum + target) % 2 == 1){
return 0;
}
int x = (sum+target)/2;
int[] dp = new int[x+1];
//01背包问题
//dp[j]表示0~i中选择的数，凑成j的方法
//初始化 nums[0]
dp[0] = 1;
for(int i=0; i<nums.Length; i++){
for(int j=x; j>=0; j--){
if(j>=nums[i]){
//不选自己，或者选择自己
dp[j] = dp[j] + dp[j-nums[i]];
}
}
}
return dp[x];
}
}
思路3：回溯法
csharp
public class Solution {
int count = 0;
public void dfs(int[] nums, int target, int index, int sum) {
if (index == nums.Length) {
//回溯到最后一位，如果 sum == target 则 count++
if (sum == target) {
count++;
}
} else {
dfs(nums, target, index + 1, sum + nums[index]);
dfs(nums, target, index + 1, sum - nums[index]);
}
}
public int FindTargetSumWays(int[] nums, int target) {
dfs(nums, target, 0, 0);
return count;
}
}
复习回溯：20220515
csharp
public class Solution {
int count;
private void dfs(int[] nums, int begin, int target){
if(begin == nums.Length){
if(target == 0){
count++;
}
return;
}
dfs(nums,begin+1,target-nums[begin]);
dfs(nums,begin+1,target+nums[begin]);
}
public int FindTargetSumWays(int[] nums, int target) {
//使用 dfs
dfs(nums,0,target);
return count;
}
}
复习01背包
csharp
public class Solution {
public int FindTargetSumWays(int[] nums, int target) {
// 转为为01背包问题
// 假设转换完成后会有两个部分，整数部分和负数部分 sumA + sumB = target
// sumA 为整数部分 subB 为负数部分，我们要找寻等式成立的情况
// 因为原来数值总和是 sum 所以就有 sumA - sumB = sum , 等于把负数的 sumB 都变成正号
// 两个等式合并 有 2 * sumA = (target + sum), sumA = (target + sum) / 2;
// 所以就转化为从nums中选择和为 sumA 的方法数，01背包问题
int sum = nums.Sum();
// 越界判断，如果 target > sum 或者 小于 -sum 说明肯定凑不起来
// 不能正好整除为2，说明也凑不起来
if(target > sum || target < -sum || (sum + target) % 2 == 1){
return 0;
}
int sumA = (target + sum) / 2;
int[] dp = new int[sumA+1]; //dp[j]表示选择数字能组成和j的方案数
dp[0] = 1; //初始化,组成0的方案数是1
for(int i=0; i<nums.Length; i++){
for(int j=sumA; j>=0; j--){
if(j >= nums[i]){
dp[j] = dp[j] + dp[j-nums[i]];
}
}
}
return dp[sumA];
}
}
复习回溯:20220629
csharp
public class Solution {
//思路1：回溯法，数据集比较小，可以尝试回溯法
int count = 0;
private void dfs(int[] nums, int begin, int target){
if(begin == nums.Length){
if(target == 0){
count++;
}
return;
}
dfs(nums,begin+1,target-nums[begin]); //符号在此处体现
dfs(nums,begin+1,target+nums[begin]);
}
public int FindTargetSumWays(int[] nums, int target) {
dfs(nums,0,target);
return count;
}
}
复习01背包：20220629
注意越界判断
csharp
public class Solution {
public int FindTargetSumWays(int[] nums, int target) {
//添加正负号之后，和分为两部分，正数部分和负数部分 sumA + sumB = target
//原先的和 sum = sumA - sumB
//合并的 sumA = (sum + target) / 2
//问题转为01背包，即从数组中选择数组凑成 sumA 的方法数
int sum = nums.Sum();
// 越界判断，如果 target > sum 或者 小于 -sum 说明肯定凑不起来
// 不能正好整除为2，说明也凑不起来
if(target > sum || target < -sum || (sum + target) % 2 == 1){
return 0;
}
int sumA = (sum + target) / 2;
int[] dp = new int[sumA+1];
dp[0] = 1; //从中间选择0个数可以凑成0，方案数为1
for(int i=0; i<nums.Length; i++){ //遍历物品
for(int j=sumA; j>=0; j--){
if(j >= nums[i]){
dp[j] = dp[j] + dp[j-nums[i]];
}
}
}
return dp[sumA];
}
}