力扣:494. 目标和(动态规划)(01背包)

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

题目:

给你一个非负整数数组 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

思路:

本题可以用回溯来解决(但是会超时),也可以用动态规划中的01背包来解决,
如何转化为01背包问题呢。

假设加法的总和为x,那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为,装满容量为x的背包,有几种方法。

这里的x,就是bagSize,也就是我们后面要求的背包容量。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了,例如sum 是5,S是2的话其实就是无解的,所以:

        # 如果nums的和与target的和的奇偶性不同,无法得到目标和为target的子集
        if (sum(nums) + target) % 2 == 1:
            return 0

同时如果 S的绝对值已经大于sum,那么也是没有方案的。

        # 如果目标和的绝对值大于nums的和,无法得到目标和为target的子集
        if abs(target) > sum(nums):
            return 0

再回归到01背包问题,为什么是01背包呢?

因为每个物品(题目中的1)只用一次

这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

动态规划五部曲

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

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

  1. 确定递推公式

有哪些来源可以推出dp[j]呢?

只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。

例如:dp[j],j 为5,

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 dp[5]。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 dp[5]。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 dp[5]。
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 dp[5]。
  • 已经有一个5(nums[i]) 的话,有 dp[0]中方法 凑成 dp[5]。

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

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

这个跟爬楼梯(力扣:70爬楼梯)和不同路径(力扣:62.不同路径)的思路有点类似,现在在重新分析一下:
现在有dp[4]种方法凑成4,你手上还有一个数字1,那么凑成5的话有几种方法? 还是dp[4]种方法!为什么不是dp[4] + 1 种方法呢?因为这个数字1是确定只能是+1,而不能是-1,只有一种方法使4变成5。可以这样理解,这里的方法数量最后是dp[4] * 1,
如果这里1可以是+1也可以是-1的话那方法数量应该是dp[4] * 2

同理,有dp[3]种方法凑成3,现在手上还有一个2,那么有几种方法凑成5?还是dp[3]种!

  1. dp数组如何初始化

从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。

这里有录友可能认为从dp数组定义来说 dp[0] 应该是0,也有录友认为dp[0]应该是1。

其实不要硬去解释它的含义,咱就把 dp[0]的情况带入本题看看应该等于多少。

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

所以本题我们应该初始化 dp[0] 为 1。

  1. 确定遍历顺序

毋庸置疑,对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。

  1. 举例推导dp数组

输入:nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下:
力扣:494. 目标和(动态规划)(01背包),python,算法,leetcode,动态规划,python,算法

代码及详细注释:

一维dp数组:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 如果nums的和与target的和的奇偶性不同,无法得到目标和为target的子集
        if (sum(nums) + target) % 2 == 1:
            return 0
        # 如果目标和的绝对值大于nums的和,无法得到目标和为target的子集
        if abs(target) > sum(nums):
            return 0
        # 计算S,S为目标和
        S = (target + sum(nums)) // 2
        # 创建一个长度为S+1的数组dp,用于记录可以得到和为i的子集的个数
        dp = [0] * (S + 1)
        dp[0] = 1  # 初始化dp[0]为1
        # 遍历nums中的每个数字
        for i in range(len(nums)):
            # 从S到nums[i]遍历,更新dp数组
            for j in range(S, nums[i] - 1, -1):
                # 更新dp[j]的值
                dp[j] += dp[j - nums[i]]
        # 返回dp[S],表示可以得到和为S的子集的个数
        return dp[S]

  • 时间复杂度:O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(m),m为背包容量

回溯版本:文章来源地址https://www.toymoban.com/news/detail-812417.html

class Solution:


    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])  # 将当前路径的副本添加到结果中
        # 如果 sum + candidates[i] > target,则停止遍历
        for i in range(startIndex, len(candidates)):
            if total + candidates[i] > target:
                break
            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if target > total:
            return 0  # 此时没有方案
        if (target + total) % 2 != 0:
            return 0  # 此时没有方案,两个整数相加时要注意数值溢出的问题
        bagSize = (target + total) // 2  # 转化为组合总和问题,bagSize就是目标和

        # 以下是回溯法代码
        result = []
        nums.sort()  # 需要对nums进行排序
        self.backtracking(nums, bagSize, 0, 0, [], result)
        return len(result)


到了这里,关于力扣:494. 目标和(动态规划)(01背包)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 动态规划 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日
    浏览(61)
  • leetCode 2915. 和为目标值的最长子序列的长度 + 动态规划 +01背包 + 空间优化 + 记忆化搜索 + 递推

    2915. 和为目标值的最长子序列的长度 - 力扣(LeetCode) 给你一个下标从  0  开始的整数数组  nums  和一个整数  target  。返回和为  target  的  nums  子序列中,子序列  长度的最大值  。如果不存在和为  target  的子序列,返回  -1  。 子序列  指的是从原数组中删除一些

    2024年02月06日
    浏览(43)
  • 力扣:474. 一和零(动态规划)(01背包)

    给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。 示例 1 : 输入: strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3 输出:

    2024年01月22日
    浏览(36)
  • 力扣第474题 一和零 c++ 动态规划 01背包

    474. 一和零 中等 相关标签 数组   字符串   动态规划 给你一个二进制字符串数组  strs  和两个整数  m  和  n  。 请你找出并返回  strs  的最大子集的长度,该子集中  最多  有  m  个  0  和  n  个  1  。 如果  x  的所有元素也是  y  的元素,集合  x  是集合  y

    2024年02月06日
    浏览(38)
  • 【Day43】代码随想录之动态规划0-1背包_1049. 最后一块石头的重量 II_494. 目标和_ 474.一和零

    动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。 初始化dp数组。 确定遍历顺序:从前到后or其他。 打印。 出现结果不正确: 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。 打印dp日志和

    2024年02月22日
    浏览(50)
  • 力扣第1049题 最后一块石头的重量Il c++ 动态规划(01背包)

    1049. 最后一块石头的重量 II 中等 相关标签 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x

    2024年02月06日
    浏览(45)
  • 算法竞赛必考算法——动态规划(01背包和完全背包)

    1.1题目介绍 1.2思路一介绍(二维数组) 代码如下: 1.3思路二介绍(一维数组) 空间优化   为什么可以使用一维数组?   我们先来看一看01背包问题的状态转移方程,我们可以发现 f[i]只用到了f[i-1],其他的是没有用到的,我们可以用滚动数组来做。   还有一个原因就是我

    2024年02月02日
    浏览(43)
  • 算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II)

    494. 目标和 - 力扣(LeetCode) 描述 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “

    2024年04月14日
    浏览(57)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(56)
  • 算法学习笔记(动态规划——01背包)

    先来聊聊动态规划,动态规划是分治法的一种体现,把一个问题分解成若干个子集,通过当前状态,经过操作得到下一个状态,最后得到最优问题解的一种方法。 步骤: 设定状态,保存状态 根据状态设定转移方程 确定边界 其中的01背包解决的是关于选择的动态规划问题,

    2024年03月25日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包