虚拟主机怎么上传网站,室内装修设计师,网站开发概述,珠海网站建设科技公司题目
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘’ 或 ‘-’ #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 ‘’ #xff0c;在 1 之前添…题目
给你一个非负整数数组 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
思路
方法一使用递归 方法二使用动态规划记数组的元素和为 sum添加 - 号的元素之和为 a则其余添加 的元素之和为 sum−a得到的表达式的结果为(sum-a)-a sum - 2a target , res ! -1检查memo数组是否已缓存了该子问题的解。如果有直接返回c nums[i]表示当前元素值大于负载值,无法选择当前元素。直接递归处理下一元素如果negatives无法选择当前元素,考虑两种选择: 1不选择当前元素,递归处理下一元素dfs(dfs, i-1, c) 。 2选择当前元素,负载减去该元素值,递归dfs(dfs, i-1, c-nums[i])则两种选择的方案数相加就是包含和不包含当前元素的总方案数。
代码
方法一
class Solution {
public:int count 0;int findTargetSumWays(vectorint nums, int target) {backtrack(nums, target, 0, 0);return count;}void backtrack(vectorint nums, int target, int index, int sum) {if (index nums.size()) {if (sum target) {count;}} else {backtrack(nums, target, index 1, sum nums[index]);backtrack(nums, target, index 1, sum - nums[index]);}}
};
方法二
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int s reduce(nums.begin(), nums.end(), 0) - abs(target);if (s 0 || s % 2)return 0;int m s / 2;int n nums.size();vectorvectorint memo(n, vectorint(m 1, -1));auto dfs [](auto dfs, int i, int c) - int {if (i 0)return c 0;int res memo[i][c];if (res ! -1)return res;if (c nums[i]) {return res dfs(dfs, i - 1, c);}return res dfs(dfs, i - 1, c) dfs(dfs, i - 1, c - nums[i]);};return dfs(dfs, n - 1, m);}
};总结
使用回溯可以遍历不同的方案问题转化成在数组 nums 中选取若干元素使得这些元素之和等于 ’ - ’ 次数计算选取元素的方案数就可以使用动态规划了
