当前位置: 首页> 健康> 美食 > 俄罗斯乌克兰克里米亚_外贸全网营销_广州百度网站排名优化_北京环球影城每日客流怎么看

俄罗斯乌克兰克里米亚_外贸全网营销_广州百度网站排名优化_北京环球影城每日客流怎么看

时间:2025/7/13 8:27:25来源:https://blog.csdn.net/Ct314/article/details/143651034 浏览次数:0次
俄罗斯乌克兰克里米亚_外贸全网营销_广州百度网站排名优化_北京环球影城每日客流怎么看

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

DP:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int total = 0;for(int n : nums){total += n;}if((total + target) % 2 != 0 || total < abs(target)){return 0;}int sub = (total + target) / 2;vector<int> dp(sub + 1, 0);dp[0] = 1;for(int n : nums){for(int j = sub; j >= n; j--){dp[j] += dp[j - n];}}return dp[sub];}};

(total + target) % 2 != 0

如果 total + target 是奇数,那么无法将它分割成两部分,返回 0


nums 划分为两个子集:一个子集 P 代表带正号的部分。另一个子集 N 代表带负号的部分。

根据题目要求,这两个子集满足:

  • P − N=target
  • P + N = sum(nums)

通过这两个方程,我们可以推导出 P 的值:

  • P =(sum(nums) + target) / 2

为了确保 P 是一个整数,(sum(nums) + target) 必须是偶数。如果 (sum(nums) + target) 是奇数,那么 P 就会是一个小数,在这种情况下,问题无解,直接返回 0

total < abs(target)

如果 total 小于 target 的绝对值,则无法通过 +- 来组合出 target,所以直接返回 0

这就变成了一个子集和问题:计算所有可以构成和为 sub 的子集数目。

定义dp[i] 表示可以组成和为 i 的子集数目。

初始时,dp[0] = 1,表示可以通过一个空集来组成和为 0 的子集。所有其他 dp[i](对于 i > 0)都为 0,因为还没有计算任何子集。

为什么从 sub 开始倒序遍历?

  • 为了避免当前的元素 n 被重复使用。假设我们正在处理元素 n 并且当前正在更新 dp[j],如果我们从 dp[sub] 开始遍历并往下计算,就可以确保每次计算时,dp[j - n] 只会使用上一轮的值。
  • 如果我们从小到大遍历,可能会在同一轮循环中多次使用同一个元素 n,这会导致错误的计算。

dp[j] += dp[j - n] 的含义:

  • dp[j - n] 代表当前元素 n 加入之前,可以组成和为 j - n 的子集数量。
  • 加上 n 后,和变为 j,因此可以通过将 dp[j - n] 加到 dp[j] 上,来表示有多少个子集和为 j
  • 换句话说,dp[j] 就是之前可以组成和为 j - n 的子集数目与当前元素 n 组合后组成和为 j 的子集数目的和。

举个例子:

nums = [1, 2, 3], sub = 4,那么 dp 数组初始化为:

dp = [1, 0, 0, 0, 0]  

第一次循环,n = 1

dp[4] += dp[4 - 1] = dp[3]dp[4] = 0

dp[3] += dp[3 - 1] = dp[2]dp[3] = 0

dp[2] += dp[2 - 1] = dp[1]dp[2] = 0

dp[1] += dp[1 - 1] = dp[0]dp[1] = 1

第二次循环,n = 2

dp[4] += dp[4 - 2] = dp[2]dp[4] = 0

dp[3] += dp[3 - 2] = dp[1]dp[3] = 1

dp[2] += dp[2 - 2] = dp[0]dp[2] = 1

第三次循环,n = 3

dp[4] += dp[4 - 3] = dp[1]dp[4] = 1

dp[3] += dp[3 - 3] = dp[0]dp[3] = 2

最后:

dp = [1, 1, 1, 2, 1] ,    dp[sub] = dp[4] = 1

DFS:

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {return dfs(nums, target, 0, 0);}int dfs(vector<int>& nums, int target, int i, int sum){if(i == nums.size()){return sum == target ? 1 : 0;}int a = dfs(nums, target, i + 1, sum + nums[i]);int b = dfs(nums, target, i + 1, sum - nums[i]);return a + b;}
};

关键字:俄罗斯乌克兰克里米亚_外贸全网营销_广州百度网站排名优化_北京环球影城每日客流怎么看

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: