南京网站制作工具,网站链接,域名流量查询工具,网站开发 属于研发费用吗题目
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 #xff0c;在 1 之前添加 - #x…题目
给你一个非负整数数组 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 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000 解答
源代码
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int num : nums) {sum num;}if (sum - target 0 || (sum - target) % 2 1) {return 0;}int len nums.length, neg (sum - target) / 2;int[][] dp new int[len 1][neg 1];dp[0][0] 1;for (int i 1; i len 1; i) {int num nums[i - 1];for (int j 0; j neg 1; j) {dp[i][j] dp[i - 1][j];if (j num) {dp[i][j] dp[i - 1][j - num];}}}return dp[len][neg];}
}
总结
记数组的元素和为 sum添加 - 号的元素之和为 neg则其余添加 的元素之和为 sum−neg得到的表达式的结果为
(sum − neg) − neg sum − 2 * neg target 即 neg (sum − target) / 2
由于数组 nums 中的元素都是非负整数neg 也必须是非负整数所以上式成立的前提是 sum − target 是非负偶数。若不符合该条件可直接返回 0。
若上式成立问题转化成在数组 nums 中选取若干元素使得这些元素之和等于 neg计算选取元素的方案数。我们可以使用动态规划的方法求解。
定义二维数组 dp其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n则最终答案为 dp[n][neg]。
当没有任何元素可以选取时元素和只能是 0对应的方案数是 1因此动态规划的边界条件是
当j 0时dp[0][j] 1当j 0时dp[0][j] 0
当 1 ≤ i ≤ n 时对于数组 nums 中的第 i 个元素 numi 的计数从 1 开始遍历 0 ≤ j ≤ neg计算 dp[i][j] 的值
如果 j num则不能选 num此时有 dp[i][j] dp[i − 1][j]
如果 j ≥ num则如果不选 num方案数是 dp[i−1][j]如果选 num方案数是 dp[i − 1][j − num]此时有 dp[i][j]dp[i − 1][j] dp[i − 1][j − num]。
因此状态转移如下
当j nums[i]时dp[i][j] dp[i−1][j]当j nums[i]时 dp[i][j] dp[i - 1][j] dp[i − 1][j − nums[i]]。
最终得到 dp[n][neg] 的值即为答案。
