LeetCode---494目标和-Toy模板网

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

494. 目标和

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

解析：01 背包问题：

1. 如何转化为01背包问题呢。

nums数组和为sum;

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

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

x = (target + sum) / 2

2 .初始化dp[0]=1 ;因为不管成与不成，总会有一种情况。

3. 因为统计的是d文章来源地址https://www.toymoban.com/news/detail-445647.html

 public int findTargetSumWays(int[] nums,int target){

        int sum=0;
        for (int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        /**
         不符合条件，凑不成target
         */
        if ((target + sum) % 2 == 1){
            return 0;
        }
        /**
         * target大于sum
         */
        if (Math.abs(target) > sum){
            return 0;
        }
        //加法的总和为bagsize；
        int bagsize=(sum + target) /2;

        //确定dp
        int[] dp=new int[bagsize + 1];

        //初始化dp
        dp[0]=1;

        for (int i=0;i<nums.length;i++){
            for (int j =bagsize ;j>=nums[i];j--){
                dp[j]+=dp[j- nums[i]];//统计总和所以是加法；
            }
        }
        return dp[bagsize];
    }

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