目录
题目来源
题目描述
示例
提示
题目解析
算法源码
题目来源
494. 目标和 - 力扣(LeetCode)
题目描述
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例
输入 | 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 |
输入 | nums = [1], target = 1 |
输出 | 1 |
解释 | 无 |
提示
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
题目解析
题目中说:
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式
其实可以理解为将数组中的数分为两类:+号的一类positive,-号的一类negative,因此可得公式如下:
- positive + negative = sum(nums)
- positive - negative = target
根据上面公式可得: positive = (sum(nums) + target) / 2
而sum(nums)、target都是给定的值,因此本题可以转化为,从nums数组中选出任意个数,只要选出的数之和为 (sum(nums) + target) / 2 即可。
由于本题中所有数都是整数,因此选出任意个数的和也一定是整数,如果(sum(nums) + target) / 2结果不是整数,则说明无法选出对应组合,此时应该返回0。
如果(sum(nums) + target) / 2的结果是整数,那么本题其实就可以转化为01背包问题:
有nums种物品,每种物品只有一个,每种物品的重量是nums[i],有一个背包,背包承重是(sum(nums) + target) / 2,现在问有多少种装满背包的方式?
可以发现,上面的求解还是有别于一般的01背包问题的,一般的01背包问题是:
有N种物品,每种物品只有一个,每种物品的重量为w[i],价值为p[i],有一个背包,背包承重是W,问背包装入物品的最大价值是多少?
其实上面两个问题都是01背包问题,01背包问题通常有三类:
- 背包能装入物品的最大价值
- 背包是否可以装满
- 背包装满有多少种方式
本题属于01背包的第三种问题,即背包装满有多少种方式。
我们假设 dp[i][j] 表示:”从0 ~ i 物品中选择任意物品,能够装满容量 j 的背包 “ 的装满背包的方案的个数。
那么按照01背包的思维,第 i 个物品我们可以选择装入或者不装入,那么:
- 第 i 个物品我选择装入的话,那么此时dp[i][j]有多少种?
- 第 i 个物品我们选择不装入的话,那么此时dp[i][j]又有多少种?
如果第 i 个物品不装入,那么dp[i][j]装满背包的方案数其实就等价于dp[i-1][j]装满背包的方案数,即此时:dp[i][j] = dp[i-1][j]
举个例子:
你有三件物品,重量分别为2,3,5,你有一个背包,承重为5,那么现在有两种方式装满背包:
- 装入2,3
- 装入5
然后又新增了一个物品,重量为x,但是目前这个x已经确定不装入背包了,那么这四件物品2,3,5,x,能够装满背包5的方案数其实还是两种。
如果第 i 个物品装入,那么dp[i][j] 装满背包的方案数其实就等价于 dp[i-1][j - nums[i]] 装满背包的方案数,即此时:dp[i][j] = dp[i-1][j - nums[i]]
举个例子:
你有三件物品,重量分别为2,3,5,你有一个背包,承重为5,那么现在有两种方式装满背包:
- 装入2,3
- 装入5
然后又新增了一个物品,重量为x,并且背包的承重也增加了x(背包承重从 j - nums[i] 变为了 j ),此时依旧只有两种装满背包的方案:
- 装入2,3,x
- 装入5,x
由于我们求得是装满背包的方案数,而不是最大价值,因此这里我们不需要Math.max去取最大,而是直接求和:
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]]
当然,如果物品nums[i]重量超过了 j 背包承重,即 j - nums[i] < 0 时,此时
dp[i][j] = dp[i-1][j]
最后本题还有一个问题,那就是dp[0][0]应该初始化为多少?
这里直接给出答案:dp[0][0] = 1
可能有人会产生疑问,【从0 ~ 0 物品中选择任意物品,能够装满容量 0 的背包】的方案数有1种?难道不是0种吗?
其实我觉得0种也是符合认知的,但是在这里却不符合代码逻辑,假设dp[0][0] = 0,那么dp[1][1]等于多少呢?
根据前面的状态转义公式,此时dp[1][1] = 0,但是实际上
【从0 ~ 1 物品中选择任意物品,能够装满容量 1 的背包】的方案数是有可能为1种的。因此本题dp[0][0]需要初始化为1。
Java算法源码
01背包二维数组解法
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int num : nums) sum += num;
if((sum + target) % 2 != 0) return 0;
int bag = (sum + target) / 2;
if(bag < 0) return 0;
int n = nums.length;
int[][] dp = new int[n+1][bag+1];
dp[0][0] = 1;
for(int i=1; i<=n; i++) {
int num = nums[i-1];
for(int j=0; j<=bag; j++) {
if(j < num) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i-1][j-num];
}
}
}
return dp[n][bag];
}
}
01背包滚动数组优化文章来源:https://www.toymoban.com/news/detail-659467.html
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int num : nums) sum += num;
if((sum + target) % 2 != 0) return 0;
int bag = (sum + target) / 2;
if(bag < 0) return 0;
int n = nums.length;
int[] dp = new int[bag+1];
dp[0] = 1;
for(int i=1; i<=n; i++) {
int num = nums[i-1];
for(int j=bag; j>=num; j--) {
dp[j] = dp[j] + dp[j-num];
}
}
return dp[bag];
}
}
JS算法源码
01背包二维数组解法
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
const sum = nums.reduce((a,b) => a + b);
if((sum + target) % 2 != 0) return 0;
const bag = (sum + target) / 2;
if(bag < 0) return 0;
const n = nums.length;
const dp = new Array(n+1).fill(0).map(() => new Array(bag+1).fill(0));
dp[0][0] = 1;
for(let i=1; i<=n; i++) {
const num = nums[i-1];
for(let j=0; j<=bag; j++) {
if(j < num) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i-1][j - num];
}
}
}
return dp.at(-1).at(-1);
};
01背包滚动数组优化
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let sum = 0;
for(let num of nums) sum += num;
if((sum + target) % 2 != 0) return 0;
const bag = (sum + target) / 2;
if(bag < 0) return 0;
const dp = new Array(bag+1).fill(0);
dp[0] = 1;
for(let i=1; i<=nums.length; i++) {
const num = nums[i-1];
for(let j=bag; j>=num; j--) {
dp[j] = dp[j] + dp[j - num];
}
}
return dp.at(-1);
};
Python算法源码
01背包二维数组解法
class Solution(object):
def findTargetSumWays(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
total = sum(nums)
if (total + target) % 2 != 0:
return 0
bag = (total + target) // 2
if bag < 0:
return 0
n = len(nums)
dp = [[0]*(bag+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
num = nums[i-1]
for j in range(0, bag+1):
if j < num:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i-1][j - num]
return dp[-1][-1]
01背包滚动数组优化
class Solution(object):
def findTargetSumWays(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
total = sum(nums)
if (total + target) % 2 != 0:
return 0
bag = (total + target) // 2
if bag < 0:
return 0
n = len(nums)
dp = [0]*(bag+1)
dp[0] = 1
for i in range(1, n+1):
num = nums[i-1]
for j in range(bag, num-1, -1):
dp[j] = dp[j] + dp[j - num]
return dp[-1]
文章来源地址https://www.toymoban.com/news/detail-659467.html
到了这里,关于LeetCode - 494 目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!