做网站的费用记什么会计科目企业网站的建立网络虚拟社区时对于企业

494. 目标和 - 力扣（LeetCode）

给你一个非负整数数组 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

思路整理：可以将集合分为两个集合，一个加法集合（left），一个减法集合（right）

可以求出加法集合（left），将问题转换为求出left这个集合。详细讲解看下文~

left:表示加法集合
right:表示减法集合left + right = sum
left - right = target
left = (sum + target) / 2集合{1 1 1 1 1}，分成left 和 right，生成的target如下：  
left(加法集合)    right(减法集合)          target4                    1                   -33                    2                    12                    3                   -11                    4                   -3sum = 5
left = (sum + target) / 2
(O_O)?
发现并没有target = 2，于是当target = 2时，left = (2+5)/2 = 7/2 无法整除,
也就是 7 % 2 == 1 直接就 return 0 就好了表示找不出这样的集合能满足 left - right = target 
此时问题转化为求出left这个集合，也就是说这个容器，
问在这个集合里边的所有元素装满这个容器有多少种方法？（妙啊~）有多少个元素能装满这个容器，我们就能找到符合这个题目条件的多少种
组合。此时发现这有点类似背包问题。那么left就是背包的容量，
集合{1 1 1 1 1}是物品集合

例子： nums = [1,2,1,3,1]，target = -2，当这种情况的时候，left=3

（1）二维dp数组

dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数

比如说我们要计算元素之和 等于 3 的方案数，由于

0 + 3 = 3

1 + 2 = 3

2 + 1 = 3

所以我们可以把元素之和 等于 0，1，2的方案数分别计算出来，然后再相加就可以得到元素之和等于3的方案数。 

 

当nums[0]=1时，

• nums[0]放不进去容量为0的背包

        j=0,j<nums[0],那么dp[1][0] = dp[0][0] = 1

• nums[0]放得进去容量为1、2、3的背包

        j=1,j>=nums[0],那么dp[1][1] = dp[0][1] + dp[0][1-nums[0]] = 0 + dp[0][0] = 0 + 1 = 1

        j=2,j>=nums[0],那么dp[1][2] = dp[0][2] + dp[0][2-nums[0]] = 0 + dp[0][1] = 0 + 0 = 0

        j=3,j>=nums[0],那么dp[1][3] = dp[0][3] + dp[0][3-nums[0]] = 0 + dp[0][2] = 0 + 0 = 0

以此类推~

 思考🤔

当 j < nums[i-1]时
① dp[i][j] = dp[i-1][j]; //"copy"当j >= nums[i-1]时
② dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];将①和②整合起来
dp[i][j] = dp[i-1][j];
if(j>=nums[i-1]) {dp[i][j] += dp[i-1][j-nums[i-1]];
}

// 二维dp数组
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;int n = nums.size();int left = 0,right = 0;for(int i=0;i<n;i++) {    sum += nums[i];}if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案left = (sum + target) / 2;vector<vector<int>> dp(n + 1, vector<int>(left + 1));dp[0][0] = 1;for (int i = 1; i <= n; i++) { // 物品for (int j = 0; j <= left; j++) { // 背包dp[i][j] = dp[i - 1][j];if (j >= nums[i-1]) {dp[i][j] += dp[i - 1][j - nums[i-1]];}}}return dp[n][left];}
};

 思考🤔,压缩状态，将二维dp数组 优化为 一维dp数组

将二维dp数组压缩成一维dp数组！！！ （重复利用实现滚动数组）

dp[j] += dp[j-nums[i]];dp[j]                装满容量为j的背包      有dp[j]种方法↑
dp[j-nums[i]]         nums[i]     dp[j-nums[i]]      1              dp[4]           凑成 dp[5]2              dp[3]           凑成 dp[5]3              dp[2]           凑成 dp[5]4              dp[1]           凑成 dp[5]5              dp[0]           凑成 dp[5]dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]也就是dp[j] += dp[j-nums[i]];初始化:dp[0] = 1
集合{0} target = 0 此时dp[0] = 1

// 一维dp数组
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;int left = 0,right = 0;for(int i=0;i<nums.size();i++) {    sum += nums[i];}if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案left = (sum + target) / 2;vector<int> dp(left+1,0);dp[0] = 1;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];}
};