- 目标总和
给你一个整数数组 nums 和一个整数目标。
您想要通过在 nums 中的每个整数之前添加符号“+”和“-”之一来构建 nums 的表达式,然后连接所有整数。
例如,如果 nums = [2, 1],您可以在 2 之前添加一个“+”,在 1 之前添加一个“-”,并将它们连接起来构建表达式“+2-1”。
返回您可以构建的不同表达式的数量,其计算结果为目标。
示例1:
输入:nums = [1,1,1,1,1],目标 = 3
输出:5
说明:有 5 种分配符号的方法,使 nums 的总和为目标 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],目标 = 1
输出:1
限制:
1
0
0
-1000
原始页面
尽管回溯在这里很有用,我们可以使用动态规划来解决这个问题,以实现更低的时间复杂度。
public int findTargetSumWays(int[] nums, int target) {
/**
sum(neg) + sum(pos) = sum(nums);
sum(pos) - sum(neg) = target;
sum(pos) = (sum(nums) + target) / 2
*/
int sum = Arrays.stream(nums).sum();
// that means the sum of the positive number is invalid, because the nums do not conclude float
if((sum+target)%2 != 0|| Math.abs(target) > sum){
return 0;
}
// here we find the summary of the positive numbers
int pos = (sum + target) >>1;
// dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods
int[][] dp = new int[nums.length+1][pos+1];
// if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
dp[0][0] = 1;
// if(nums[0] j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
// Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
return dp[nums.length][pos];
}
登录后复制
笔记
1、初始化dp数组很重要尤其是这里重要的是要弄清楚0的含义
以上就是LeetCode DayDynamic Programming Part 4的详细内容,更多请关注php中文网其它相关文章!
91资源网站长-冰晨2024-08-27 17:15
发表在:【账号直充】爱奇艺黄金VIP会员『1个月』官方直充丨立即到账丨24小时全天秒单!不错不错,价格比官方便宜
91资源网站长-冰晨2024-08-27 16:15
发表在:2022零基础Java入门视频课程不错,学习一下