LeetCode-494. 目标和

川长思鸟来 2024-03-25 10:45 72阅读 0赞

题目来源  
[494. 目标和][494.]

### 思路 ###

*  01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。 假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。 我们想要的 S = 正数和 - 负数和 = x - y 而已知x与y的和是数组总和：x + y = sum 可以求出 x = (S + sum) / 2 = target 也就是我们要从nums数组里选出几个数，令其和为target 于是就转化成了求容量为target的01背包问题 =>要装满容量为target的背包，有几种方案
 *  特例判断 如果S大于sum，不可能实现，返回0 如果x不是整数，也就是S + sum不是偶数，不可能实现，返回0

**看的时候没看太明白，我再重新描述一遍**，把数组里的所有数字分成两个部分，一部分的和为x，一部分的和为y。所以x+y就等于数组的总和sum。因为s<=sum的，所以我们要让一部分数字为负数，就让y为负数，所以x-y=s。我们的重点就转移到x上了，求数组里和为x的情况。（x=(sum+s)/2）

### 回溯法 ###

class Solution {
        
        int ans = 0;
        public int findTargetSumWays(int[] nums, int target) {
        
            if(nums == null){
        
                return 0;
            }
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if((target+sum)%2 == 1){
        
                return 0;
            }
            int bagSize = (target+sum)/2;
            backTracking(nums,bagSize,0,0);
            return ans;
        }
    
        public void backTracking(int[] nums,int bagSize,int startIndex,int sum){
        
            if(sum == bagSize){
        
                ans += 1;
            }
            if(sum > bagSize){
        
                return;
            }
            for(int i =startIndex;i<nums.length;i++){
        
                sum += nums[i];
                backTracking(nums,bagSize,i+1,sum);
                sum -=nums[i];
            }
        }
    }

![在这里插入图片描述][b3b757e65ae84d2e85a3fb49a4593deb.png]

做这个要注意一个问题，不能写return，可能之后还有0的情况，那么也是一种组合

if(sum == bagSize){
        
                ans += 1;
                return;
            }

![在这里插入图片描述][c1e945277fb84c37ba18b188c3646665.png]

### 动态规划 ###

class Solution {
        
        public int findTargetSumWays(int[] nums, int target) {
        
            if(nums == null){
        
                return 0;
            }
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            //target的绝对值已经大于sum
            if(Math.abs(target)>sum){
        
                return 0;
            }
            if((target+sum)%2 == 1){
        
                return 0;
            }
            int bagSize = (target+sum)/2;
            int[][] dp = new int[nums.length][bagSize+1];
            dp[0][0] = 1;
            for(int j = 0;j<=bagSize;j++){
        
                if(j == nums[0]){
        
                    dp[0][j]++;
                }
            }
            for(int i = 1;i<nums.length;i++){
        
                for(int j = 0;j<=bagSize;j++){
        
                    if(j<nums[i]){
        
                        dp[i][j] = dp[i-1][j];
                    }else{
        
                        dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]];
                    }
                }
            }
            return dp[nums.length-1][bagSize];
        }
    }

![在这里插入图片描述][3dab1481c78240de9bc6401d826ca154.png]

### 动态规划(压缩) ###

*  1.确定dp数组以及下标的含义

dp\[j\] 表示：填满j（包括j）这么大容积的包，有dp\[j\]种方法

*  2.确定递推公式

只要搞到nums\[i\]），凑成dp\[j\]就有dp\[j - nums\[i\]\] 种方法。  
例如：dp\[j\]，j 为5，

> 已经有一个1（nums\[i\]） 的话，有 dp\[4\]种方法 凑成 容量为5的背包。  
> 已经有一个2（nums\[i\]） 的话，有 dp\[3\]种方法 凑成 容量为5的背包。  
> 已经有一个3（nums\[i\]） 的话，有 dp\[2\]中方法 凑成 容量为5的背包  
> 已经有一个4（nums\[i\]） 的话，有 dp\[1\]中方法 凑成 容量为5的背包  
> 已经有一个5 （nums\[i\]）的话，有 dp\[0\]中方法 凑成 容量为5的背包

那么凑整dp\[5\]有多少方法呢，也就是把 所有的 dp\[j - nums\[i\]\] 累加起来。

dp[j] += dp[j - nums[i]]

dp\[j\] += dp\[j - nums\[i\]\]对这句组合数的理解： 1、如果不选第i个数（nums\[i\]）的话，则方法数为dp\[j\]； 2、如果选第i个数（nums\[i\]）的话，则方法数为dp\[j - nums\[i\]\]； 所以方法总数为：dp\[j\] = dp\[j\] + dp\[j - nums\[i\]\]；（感觉这样拆开写比较容易理解） 可以对比其他01背包问题：dp\[j\] = max(dp\[j\], dp\[j - nums\[i\]\])，这种问题即是从选i与不选i里，选取最大值。

*  3.dp数组如何初始化

如果数组\[0\] ，target = 0，那么 bagSize = (target + sum) / 2 = 0。 dp\[0\]也应该是1， 也就是说给数组里的元素 0 前面无论放加法还是减法，都是 1 种方法。

**如果是 数组\[0,0,0,0,0\] target = 0 呢。**  
其实 此时最终的dp\[0\] = 32，也就是这五个零 子集的所有组合情况，但此dp\[0\]非彼dp\[0\]，dp\[0\]能算出32，其基础是因为dp\[0\] = 1 累加起来的。  
dp\[j\]其他下标对应的数值也应该初始化为0，从递推公式也可以看出，dp\[j\]要保证是0的初始值，才能正确的由dp\[j - nums\[i\]\]推导出来。

*  4.确定遍历顺序

nums放在外循环，target在内循环，且内循环倒序。

*  5.举例推导dp数组

输入：nums: \[1, 1, 1, 1, 1\], S: 3  
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4  
dp数组状态变化如下：  
![在这里插入图片描述][9bfdf3bd70434989871806621d3060f7.png]

class Solution {
        
        public int findTargetSumWays(int[] nums, int target) {
        
            if(nums == null){
        
                return 0;
            }
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if(Math.abs(target)>sum){
        
                return 0;
            }
            if((target+sum)%2 == 1){
        
                return 0;
            }
            int bagSize = (target+sum)/2;
            int[] dp = new int[bagSize+1];
            dp[0] = 1;
            for(int i = 0;i<nums.length;i++){
        
                for(int j = bagSize;j>=nums[i];j--){
        
                    dp[j] = dp[j] + dp[j-nums[i]];
                }
            }
            return dp[bagSize];
        }
    }

![在这里插入图片描述][8daabe848353411baeffe517395994d3.png]

[494.]: https://leetcode.cn/problems/target-sum/
[b3b757e65ae84d2e85a3fb49a4593deb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7c9441b6945e47caa8044bdb02d69062.png
[c1e945277fb84c37ba18b188c3646665.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/01240fc40a314c38bae81f9e18d13ac7.png
[3dab1481c78240de9bc6401d826ca154.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1a9f541870c6488ea5e5677b5ef01c1d.png
[9bfdf3bd70434989871806621d3060f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/04748ed78cc941118c72c69406e67b4b.png
[8daabe848353411baeffe517395994d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/01a0f13a28b14198919c94e46fa23231.png