LeetCode - 494 目标和

这篇具有很好参考价值的文章主要介绍了LeetCode - 494 目标和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目来源

题目描述

示例

提示

题目解析

算法源码


题目来源

494. 目标和 - 力扣(LeetCode)

题目描述

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例

输入 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
输入 nums = [1], target = 1
输出 1
解释

提示

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

题目解析

题目中说:

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式

其实可以理解为将数组中的数分为两类:+号的一类positive,-号的一类negative,因此可得公式如下:

  • positive + negative = sum(nums)
  • positive - negative = target

根据上面公式可得: positive = (sum(nums) + target) / 2

而sum(nums)、target都是给定的值,因此本题可以转化为,从nums数组中选出任意个数,只要选出的数之和为 (sum(nums) + target) / 2 即可。

由于本题中所有数都是整数,因此选出任意个数的和也一定是整数,如果(sum(nums) + target) / 2结果不是整数,则说明无法选出对应组合,此时应该返回0。

如果(sum(nums) + target) / 2的结果是整数,那么本题其实就可以转化为01背包问题:

有nums种物品,每种物品只有一个,每种物品的重量是nums[i],有一个背包,背包承重是(sum(nums) + target) / 2,现在问有多少种装满背包的方式?

可以发现,上面的求解还是有别于一般的01背包问题的,一般的01背包问题是:

有N种物品,每种物品只有一个,每种物品的重量为w[i],价值为p[i],有一个背包,背包承重是W,问背包装入物品的最大价值是多少?

其实上面两个问题都是01背包问题,01背包问题通常有三类:

  • 背包能装入物品的最大价值
  • 背包是否可以装满
  • 背包装满有多少种方式

本题属于01背包的第三种问题,即背包装满有多少种方式。

我们假设 dp[i][j] 表示:”从0 ~ i 物品中选择任意物品,能够装满容量 j 的背包 “ 的装满背包的方案的个数

那么按照01背包的思维,第 i 个物品我们可以选择装入或者不装入,那么:

  • 第 i 个物品我选择装入的话,那么此时dp[i][j]有多少种?
  • 第 i 个物品我们选择不装入的话,那么此时dp[i][j]又有多少种?

如果第 i 个物品不装入,那么dp[i][j]装满背包的方案数其实就等价于dp[i-1][j]装满背包的方案数,即此时:dp[i][j] = dp[i-1][j]

举个例子:

你有三件物品,重量分别为2,3,5,你有一个背包,承重为5,那么现在有两种方式装满背包:

  • 装入2,3
  • 装入5

然后又新增了一个物品,重量为x,但是目前这个x已经确定不装入背包了,那么这四件物品2,3,5,x,能够装满背包5的方案数其实还是两种。

如果第 i 个物品装入,那么dp[i][j] 装满背包的方案数其实就等价于 dp[i-1][j - nums[i]] 装满背包的方案数,即此时:dp[i][j] = dp[i-1][j - nums[i]]

举个例子:

你有三件物品,重量分别为2,3,5,你有一个背包,承重为5,那么现在有两种方式装满背包:

  • 装入2,3
  • 装入5

然后又新增了一个物品,重量为x,并且背包的承重也增加了x(背包承重从 j - nums[i] 变为了 j ),此时依旧只有两种装满背包的方案:

  • 装入2,3,x
  • 装入5,x

由于我们求得是装满背包的方案数,而不是最大价值,因此这里我们不需要Math.max去取最大,而是直接求和:

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

当然,如果物品nums[i]重量超过了 j 背包承重,即 j - nums[i] < 0 时,此时

dp[i][j]  =  dp[i-1][j]

最后本题还有一个问题,那就是dp[0][0]应该初始化为多少?

这里直接给出答案:dp[0][0] = 1

可能有人会产生疑问,【从0 ~ 0 物品中选择任意物品,能够装满容量 0 的背包】的方案数有1种?难道不是0种吗?

其实我觉得0种也是符合认知的,但是在这里却不符合代码逻辑,假设dp[0][0] = 0,那么dp[1][1]等于多少呢?

根据前面的状态转义公式,此时dp[1][1] = 0,但是实际上

【从0 ~ 1 物品中选择任意物品,能够装满容量 1 的背包】的方案数是有可能为1种的。因此本题dp[0][0]需要初始化为1。

Java算法源码

01背包二维数组解法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums) sum += num;
        if((sum + target) % 2 != 0) return 0;

        int bag = (sum + target) / 2;
        if(bag < 0) return 0;

        int n = nums.length;

        int[][] dp = new int[n+1][bag+1];
        dp[0][0] = 1;

        for(int i=1; i<=n; i++) {
            int num = nums[i-1];
            for(int j=0; j<=bag; j++) {
                if(j < num) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-num];
                }
            }
        }

        return dp[n][bag];
    }
}

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript

01背包滚动数组优化

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums) sum += num;
        if((sum + target) % 2 != 0) return 0;

        int bag = (sum + target) / 2;
        if(bag < 0) return 0;

        int n = nums.length;

        int[] dp = new int[bag+1];
        dp[0] = 1;

        for(int i=1; i<=n; i++) {
            int num = nums[i-1];
            for(int j=bag; j>=num; j--) {
                dp[j] = dp[j] + dp[j-num];
            }
        }

        return dp[bag];
    }
}

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript

 

JS算法源码

01背包二维数组解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((a,b) => a + b);
    if((sum + target) % 2 != 0) return 0;

    const bag = (sum + target) / 2;
    if(bag < 0) return 0;

    const n = nums.length;

    const dp = new Array(n+1).fill(0).map(() => new Array(bag+1).fill(0));
    dp[0][0] = 1;

    for(let i=1; i<=n; i++) {
        const num = nums[i-1];
        for(let j=0; j<=bag; j++) {
            if(j < num) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j] + dp[i-1][j - num];
            }
        }
    }

    return dp.at(-1).at(-1);
};

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript

 

01背包滚动数组优化

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    let sum = 0;
    for(let num of nums) sum += num;
    if((sum + target) % 2 != 0) return 0;

    const bag = (sum + target) / 2;
    if(bag < 0) return 0;

    const dp = new Array(bag+1).fill(0);
    dp[0] = 1;

    for(let i=1; i<=nums.length; i++) {
        const num = nums[i-1];
        for(let j=bag; j>=num; j--) {
            dp[j] = dp[j] + dp[j - num];
        }
    }

    return dp.at(-1);
};

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript

 

Python算法源码

01背包二维数组解法

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        total = sum(nums)

        if (total + target) % 2 != 0:
            return 0
        
        bag = (total + target) // 2

        if bag < 0:
            return 0
        
        n = len(nums)
        
        dp = [[0]*(bag+1) for _ in range(n+1)]
        dp[0][0] = 1

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

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript

01背包滚动数组优化

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        total = sum(nums)

        if (total + target) % 2 != 0:
            return 0
        
        bag = (total + target) // 2

        if bag < 0:
            return 0
        
        n = len(nums)
        
        dp = [0]*(bag+1)
        dp[0] = 1

        for i in range(1, n+1):
            num = nums[i-1]
            for j in range(bag, num-1, -1):
                dp[j] = dp[j] + dp[j - num]
        
        return dp[-1]

LeetCode - 494 目标和,算法与数据结构,leetcode,算法,Java,Python,JavaScript文章来源地址https://www.toymoban.com/news/detail-659467.html

到了这里,关于LeetCode - 494 目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode:494.目标和

    解题思路:1.因为每个数字都有正负两种选择,所以可以采用回溯算法。(会超时) 2.分成两个集合,分别为正数集合(left)和负数(right)集合。 left + right = Sum --- right = Sum - left left - right = target 联立得到: left = (target + Sum) /  2 如果不能整除,则凑不出target dp数组含义:装

    2024年02月22日
    浏览(29)
  • 【LeetCode】494. 目标和

    首先,将这道题想成 0-1背包问题 ,我们最终要输出的结果是最多的方法数,因此 dp 数组需要记录具体的方法数。 状态定义 按照 0-1 背包问题的套路,我们将状态定义为 : dp[i][j] ,表示「前 i 个数字,和等于 j 的情况下,能够达到的不同表达式的最大数目」。 状态转移方程

    2024年02月03日
    浏览(29)
  • 动态规划 Leetcode 494 目标和

    Leetcode 494 学习记录自代码随想录 要点:1.想到±代表其实求的是连个组合的差值,进而记left为正组合,right为负组合,则有 { l e f t − r i g h t = t a r g e t l e f t + r i g h t = s u m left { begin{matrix} left-right=target \\\\ left+right=sum end{matrix} right . { l e f t − r i g h t = t a r g e t l e f t + r

    2024年04月09日
    浏览(58)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(50)
  • 【算法与数据结构】474、LeetCode一和零

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题要找strs数组的最大子集,这个子集最多含有 m m m 个0和 n n n 个1。本题也可以抽象成一个01背包的问题。其中,strs内的元素就是物品,而 m m m 和 n n n 就是背包的维度。 d p [

    2024年01月22日
    浏览(40)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(65)
  • 【算法与数据结构】343、LeetCode整数拆分

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :博主做这道题的时候一直在思考,如何找到 k k k 个正整数, k k k 究竟为多少合适。从数学的逻辑上来说,将 n n n 均分为 k k k 个数之后, k k k 个数的乘积为最大(类似于相同周长

    2024年01月17日
    浏览(51)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(50)
  • 【python与数据结构】(leetcode算法预备知识)

    笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 1.数字类型: 整数(int):表示整数值,例如 1、-5、100。 浮点数(float):表示带有小数部分的数字,例如 3.14、-0.5、2.0。 复数(complex):表示实部和虚部的复数,例如 2+3j。 2.布尔类型(bool): 表示真(True)或假(

    2024年02月08日
    浏览(38)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包