目标和
Leetcode 494
学习记录自代码随想录文章来源：https://www.toymoban.com/news/detail-845110.html
要点：1.想到±代表其实求的是连个组合的差值，进而记left为正组合，right为负组合，则有
{
l
e
f
t
−
r
i
g
h
t
=
t
a
r
g
e
t
l
e
f
t
+
r
i
g
h
t
=
s
u
m
\left \{ \begin{matrix} left-right=target \\ left+right=sum \end{matrix} \right .
{left−right=targetleft+right=sum，从而可以推导出
l
e
f
t
=
s
u
m
+
t
a
r
g
e
t
2
left = \frac{sum+target}{2}
left=2sum+target；
2.想到以上面所求left为背包容量，得到dp[j]含义为装满背包容量j的组合方法数目；
3.求组和数目的递推公式一般为
d
p
[
j
]
+
=
d
p
[
j
−
n
u
m
s
[
i
]
]
dp[j] += dp[j-nums[i]]
dp[j]+=dp[j−nums[i]]
4.dp数组初始化时dp[0]为1，其余为0否则递推公式会无效文章来源地址https://www.toymoban.com/news/detail-845110.html
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 1.一加一减两种方法实际上是将数组分为两个集合left(+),right(-)
// 则有left-right = target, 且left+right = sum, 则推出left = (sum+target)/2
int sum = 0;
for(int a : nums) sum += a;
if(sum + target < 0) return 0; // 总和小于target则无法实现结果
if((sum + target) % 2) return 0;
int left = (sum + target) / 2;
// dp[j]代表背包容量为j时填满背包有dp[j]种方法
vector<int> dp(1001, 0);
// 2.递推公式（求组和有多少种方法一般可参考此递推公式）：dp[j] += dp[j-nums[i]](对所有小于等于j的nums[i]求和)
// 3.初始化dp数组为dp[0] = 1, 其余为0
dp[0] = 1; // 若dp[0]为0则所有递推结果均为0
// 4.遍历顺序先遍历物品，再反向遍历容量
for(int i = 0; i < nums.size(); i++){
for(int j = left; j >= nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
}
};
到了这里，关于动态规划 Leetcode 494 目标和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
