【Day 62 】2023-08-10 - 494. 目标和

[azl397985856]

494. 目标和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/target-sum/

前置知识

• 背包
• 数学

  题目描述

  给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，target。现在你有两个符号  +  和  -。对于数组中的任意一个整数，你都可以从  +  或  -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 target 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], target: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

[freesan44]

class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        let totalSum = nums.reduce(0, +)
        let desiredSum = totalSum + target

        if desiredSum % 2 != 0 {
            return 0
        }

        let halfSum = desiredSum / 2
        var dp = [Int](repeating: 0, count: halfSum + 1)
        dp[0] = 1

        for i in 0..<nums.count {
            for j in (nums[i]...halfSum).reversed() {
                dp[j] += dp[j - nums[i]]
            }
        }

        return dp[halfSum]
    }
}

[Diana21170648]

思路

动态规划解决背包问题

代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        t=sum(nums)+abs(target)
        if t%2:
            return 0
        t=t//2#背包的大小
        dp=[0]*(t+1)
        dp[0]=1
        for i in range(len(nums)):
            for j in range(t,nums[i]-1,-1):
                #if j - nums[i] >= 0:
                dp[j]+=dp[j-nums[i]]
        return dp[-1]

复杂度分析

• 时间复杂度：T=O(fushu*(sum(nums)+target))/2
• 空间复杂度：S=O(sum(nums)+target)/2

[GuitarYs]

class Solution:
    def findTargetSumWays(self, nums, target):
        total_sum = sum(nums)
        if total_sum < target or (total_sum + target) % 2 != 0:
            return 0
        subset_sum = (total_sum + target) // 2
        dp = [0] * (subset_sum + 1)
        dp[0] = 1
        for num in nums:
            for i in range(subset_sum, num - 1, -1):
                dp[i] += dp[i - num]

        return dp[subset_sum]

[Fuku-L]

代码

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

[Beanza]

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

[Alexno1no2]

# 思路
# 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
# dp[j]代表的意义：填满容量为j的背包，有dp[j]种方法。因为填满容量为0的背包有且只有一种方法，所以dp[0] = 1
# 状态转移：dp[j] = dp[j] + dp[j - num]， 当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数 也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。
# 返回dp[-1]，也就是dp[target]

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        sumAll = sum(nums)
        if S > sumAll or (S + sumAll) % 2:
            return 0
        target = (S + sumAll) // 2
        if target < 0:
            return 0

        dp = [0] * (target + 1)
        dp[0] = 1
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] + dp[j - num]
        return dp[-1]

[Momogir]

记neg为负数之和，pos为正数之和
# pos + neg = target
# pos - neg = sum
# pos = (target+sum)/2
# 转换成从数值列表里面找到n个数字，使得和为pos
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        pos=(sum(nums)+target)/2
        if pos - int(pos)!=0:return 0
        else: pos=int(pos)

        n=len(nums)

        dp=[[0]*(pos+1) for _ in range(n)]

        #dp[i][j]表示第[0,i]个位置中有n种方法能找到数字使得和为j
        #初始化边界条件
        #当j=0,对应的方案为1,表示不取任何元素
        for i in range(n): dp[i][0]=1
        # 当i=0时,当nums[0]=j时候，dp[i][j]=1
        for j in range(pos+1):
            if j==nums[0]:
                dp[0][j]=1

        for i in range(1,n):
            for j in range(1,pos+1):
                if nums[i]<=j:
                     dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
                else:dp[i][j]=dp[i-1][j]
        print(dp)
        return dp[-1][-1]