您现在的位置是:首页 >其他 >494. 目标和网站首页其他
494. 目标和
目录
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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2、思路:动态规划
仔细阅读题目可以发现,可以理解为将整个数组分为两个子集,其中一个子集减去另一个子集有多少种实现方法。
假设在数字前放加号的数字总和为x,那么放减号的数字总和为sum-x,而目标target = x-(sum-x),即x = (target+sum)/2,那么就将问题转换为了动态规划。
如果 target+sum 不能整除2,那么没有方法可以实现题目要求。因为nums[i] >= 0,所以sum为非负数,所以,如果背包容量left求出小于0的数,则没有方案。
因为每个物品只能使用一次,所以,该题为01背包问题。
2.1、确定dp数组及x下标含义
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
2.2、确定递推公式
有了nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
如果已经有一个1(nums[i]) ,有 dp[4]种方法 凑成 容量为5的背包。
如果已经有一个2(nums[i]) ,有 dp[3]种方法 凑成 容量为5的背包。
如果已经有一个3(nums[i]) ,有 dp[2]中方法 凑成 容量为5的背包
如果已经有一个4(nums[i]) ,有 dp[1]中方法 凑成 容量为5的背包
如果已经有一个5 (nums[i]),有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]就是把所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式,都使用类似的方法处理:
dp[j] += dp[j - nums[i]]
2.3、dp数组初始化
当背包容量为0时,有1种方法来放物品,就是什么都不放,遇到物品再说。
所以,dp[0] 初始化为0,而其他的dp数组需要通过其他的dp数组累加计算而来,所以初始化为0.
2.4、确定遍历顺序
外层从前往后,内层从大到小。
3、C++实现如下
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int length = nums.size();
int sum = 0;
for(int i = 0;i<length;++i){
sum+=nums[i];
}
int left = target + sum;
if(left%2!=0||left<0){
return 0;
}
left/=2;
vector<int> dp(left+1);
dp[0] = 1;
for(int i = 0;i<length;++i){
for(int j = left;j>=nums[i];--j){
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
}
};