【LeetCode】494. 目标和

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

494. 目标和

【LeetCode】494. 目标和
【LeetCode】494. 目标和
【LeetCode】494. 目标和

思路

首先,将这道题想成 0-1背包问题,我们最终要输出的结果是最多的方法数,因此 dp 数组需要记录具体的方法数。

状态定义

按照 0-1 背包问题的套路,我们将状态定义为 :dp[i][j] ,表示「前 i 个数字,和等于 j 的情况下,能够达到的不同表达式的最大数目」。

状态转移方程

我们以 nums = [1, 1, 1] 为例,很容易可以发现: dp[i][j] 取决于「前 i-1 个元素的和」与「当前元素的值」的关系 ,我们要从某个值得到 j,j 可以由该值加上 nums[i]得到,也可以由该值减去 nums[i]得到 。即 dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j+nums[i-1]];

【LeetCode】494. 目标和

进一步思考:下标转换

但是从上面的例子可以看出,和可能为负数 ,而下标不可能小于 0,那么我们如何防止下标越界呢?

我们不妨改变下标的取值范围,对于 nums = [1, 1, 1] 来说,我们先计算它的最大和:3(1+1+1),记为 sum,运算结果的取值范围是:[-3,3],我们可以对这个范围的数都加上 sum ,变成 [0, 6],这样就解决了下标越界的问题。

所以最终的状态转移方程为:dp[i][j+sum] += dp[i-1][j-nums[i-1]+sum];dp[i][j+sum] += dp[i-1][j+nums[i-1]+sum]; ,凡是 j 值我都加上了 sum。

初始化

我们需要初始化 nums[0] 可以构造出的运算结果,即 dp[1][nums[0]+sum] += 1, dp[1][-nums[0]+sum] += 1;

这里需要考虑 +nums[0]-nums[0] 两种情况,我没有直接置为 1 ,是因为考虑到 nums[0] = 0 的情况,+0 和 -0 分别代表运算结果为 0 的两种表达式,这种代码书写方式更为通用。

此外,为了防止下标越界,我将 j 值加上了 sum。

最终的返回结果

最终返回 n 个数字,和等于 target 的情况下能达到的不同表达式的最大数目,同样地,target 也需要加上 sum ,即dp[n][target+sum];文章来源地址https://www.toymoban.com/news/detail-435419.html

注意点

  • 为了方便计算,我们在开头进行特殊判断如果 sum 小于 target 的绝对值,说明无法构造出表达式,直接返回 0
  • 需要判断 j 的边界,不然很容易出现下标越界的问题。

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 特判:不可能构造出表达式
        if(sum < abs(target))  return 0;

        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(sum*2+1, 0));
        // 初始化
        // 通过nums[0]能够构造出一种等于target的表达式 +1
        dp[1][nums[0]+sum] += 1, dp[1][-nums[0]+sum] += 1;

        for(int i=2; i<=n; ++i){
            for(int j=-sum; j<=sum; ++j){
                if(j-nums[i-1]+sum>=0 && j-nums[i-1]+sum<=sum*2 && dp[i-1][j-nums[i-1]+sum] > 0){
                    dp[i][j+sum] += dp[i-1][j-nums[i-1]+sum];
                }                
                if(j+nums[i-1]+sum>=0 && j+nums[i-1]+sum<=sum*2 && dp[i-1][j+nums[i-1]+sum] > 0){
                    dp[i][j+sum] += dp[i-1][j+nums[i-1]+sum];
                }
            }
        }
        return dp[n][target+sum];
    }
};

到了这里,关于【LeetCode】494. 目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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)
  • 【算法与数据结构】494、LeetCode目标和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似,同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 p o s i t i v e positive p os i t

    2024年01月20日
    浏览(45)
  • Day43|leetcode 1049.最后一块石头的重量II、494.目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 视频链接:动态规划之背包问题,这个背包最多能装多少?LeetCode:1049.最后一块石头的重量II_哔哩哔哩_bilibili 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设

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

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

    2024年04月14日
    浏览(57)
  • [Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    内容:今天复习下dp数组中的背包问题 分割等和子集 - 能否装满 最后一块石头 - 尽可能装满 目标和 - 有多少种方法装 一和零 - 装满背包有多少个物品 416. 分割等和子集 10背包:用/不用;有容量;有价值 dp[j] : 容量为j,最大价值为dp[j]         重量和价值等价 dp[target] == t

    2024年02月16日
    浏览(43)
  • 【LeetCode题目详解】第九章 动态规划 part05 1049. 最后一块石头的重量 II 494. 目标和 474.一和零(day43补)

    有一堆石头,用整数数组  stones 表示。其中  stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x 和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那么两块石头都会被完全粉碎; 如果  x != y

    2024年02月09日
    浏览(38)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(41)
  • 494. 目标和

    494. 目标和 https://leetcode.cn/problems/target-sum/description/ 首先,如果最终结果可以由其中的每一步过程,造成影响得来,那么就可以考虑用dp dp的难点就在于状态转移方程!!!如何将一个问题转化很重要!!! 转化形式应该为: 未知状态 = 已知确定目标值 dp数组过程推演情况。

    2024年02月12日
    浏览(49)
  • 力扣:494. 目标和(动态规划)(01背包)

    给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的

    2024年01月21日
    浏览(38)
  • 力扣第494题 目标和 c++ 动态规划 c++ 01背包 难~~

    494. 目标和 中等 相关标签 数组   动态规划   回溯 给你一个非负整数数组  nums  和一个整数  target  。 向数组中的每个整数前添加  \\\'+\\\'  或  \\\'-\\\'  ,然后串联起所有整数,可以构造一个  表达式  : 例如, nums = [2, 1]  ,可以在  2  之前添加  \\\'+\\\'  ,在  1  之前添加 

    2024年02月06日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包