网站营销方法,学习网首页,广东建设厅网站首页,徐州网页设计494. 目标和 文章目录 [494. 目标和](https://leetcode.cn/problems/target-sum/)一、题目二、题解方法一#xff1a;目标和路径计数算法方法二#xff1a;01背包方法三#xff1a;01背包一维数组 一、题目
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个…494. 目标和 文章目录 [494. 目标和](https://leetcode.cn/problems/target-sum/)一、题目二、题解方法一目标和路径计数算法方法二01背包方法三01背包一维数组 一、题目
给你一个非负整数数组 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 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000
二、题解
方法一目标和路径计数算法
思考过程可以分为以下几步 问题拆解 首先将问题拆解为更小的子问题。在这个问题中我们可以将目标和问题拆解为在给定数组中选择一些数字使得它们的和等于目标值。 状态定义 确定动态规划的状态。在这个问题中我们可以考虑使用二维数组 dp[i][j] 表示在前 i 个数字中和为 j 的表达式的数量。 状态转移方程 找到状态之间的转移关系。这是动态规划问题的核心。在这个问题中对于每个数字 nums[i]我们有两种选择添加正号或者添加负号。因此状态转移方程可以表示为dp[i][j] dp[i-1][j-nums[i]] dp[i-1][jnums[i]]即前 i-1 个数字和为 j-nums[i] 的表达式数量加上前 i-1 个数字和为 jnums[i] 的表达式数量最后的数字是dp[i][j] dp[i-1][abs(j-nums[i])] dp[i-1][jnums[i]]因为如果j nums[i]我们是可以通过dp[i-1][nums[i]-j]得到dp[i][j]的。举个例子如图为什么dp[2][0] 2图中已经说明白了。 边界条件 根据问题的实际情况确定边界条件。在这个问题中我们可以从第一个数字开始考虑初始化 dp[0][j]表示只有一个数字时和为 j 的表达式数量。 问题求解 根据状态转移方程和边界条件从小问题逐步求解到原问题。填充二维数组 dp最终 dp[nums.size()-1][abs(target)] 就是我们要的答案表示在所有数字中和为 target 的表达式数量。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {// 定义一个二维数组 dp大小为 (nums.size(), 2001)其中 dp[i][j] 表示在前 i 个数字中和为 j 的表达式数量vectorvectorint dp(nums.size(), vectorint(2001, 0));// 初始化处理只有一个数字的情况for(int i 0; i 1000; i){if(nums[0] i){if(nums[0] 0) dp[0][i] 2; // 对于数字 0可以有正号或负号else dp[0][i] 1;}}// 填写 dp 数组for(int i 1; i nums.size(); i){for(int j 0; j 1000; j){dp[i][j] dp[i-1][abs(j-nums[i])] dp[i-1][jnums[i]]; // 根据状态转移方程计算 dp[i][j]}}return dp[nums.size()-1][abs(target)]; // 返回在所有数字中和为 target 的表达式数量}
};方法二01背包
01背包问题通常是这样的给定一组物品每个物品有重量和价值我们要选择一些物品放入一个容量有限的背包中使得背包中物品的总重量不超过背包的容量同时最大化物品的总价值。
在这道题中我们可以将正数部分和负数部分前面是加号的和前面是减号的的数字分别看作两组物品。正数部分的数字相当于具有正的价值负数部分的数字相当于具有负的价值。
具体步骤如下 将数组 nums 拆分成两个子数组add 和 minus。add 包含所有正数部分的数字minus 包含所有负数部分的数字。 我们可以得到add-minus targetaddminus sum从而根据这两个式子得出(sumtarget)/2 add。 使用01背包的思想这个问题就转化成了所有数字凑成add这个数的方法。即背包容量是add物品是nums数组里的所有元素。 使用动态规划来解决问题我们创建一个二维数组 dp其中 dp[i][j] 表示在考虑前 i 个物品时总和等于 j 的方法数。 初始化 dp[0][0] 为 1因为当没有物品可选时总和为 0 是唯一的一种方式但如果nums[0] 0还有一种方式就是只取nums[0]则有两种方式。对于其它物品 nums[i]我们根据以下规则更新 dp[i][j] 如果 j nums[i]那么我们可以选择是否将 nums[i] 放入背包dp[i][j]等于不放入背包和放入背包方式的总和即 dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]]。如果 j nums[i]则nums[i]不可以放入背包dp[i][j] dp[i-1][j]。 最终的答案是 dp[nums.size()-1][add]表示在考虑所有物品后总和等于 add 的方法数。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;// 计算数组nums的总和for(int i 0; i nums.size(); i){sum nums[i];}// 如果总和与目标值之和为奇数或者总和小于目标值的绝对值则无解返回0if((sum target) % 2 1 || sum abs(target)){return 0;}// 计算要构造的正数部分和这是01背包问题中的背包容量int add (sum target) / 2;// 创建二维动态规划数组dpvectorvectorint dp(nums.size(),vectorint(add1, 0));// 初始化dp数组for(int i 0; i add; i){// 如果i等于第一个数字nums[0]表示可以用第一个数字构造和为i的方式有1种if(i nums[0]){dp[0][i] 1;}} // 特殊情况处理if(nums[0] 0) dp[0][0] 2;// 普通情况当没有物品可选时总和为 0 是唯一的一种方式else dp[0][0] 1;// 填写dp数组for(int i 1; i nums.size(); i){for(int j 0; j add; j){// 如果当前数字nums[i]大于目标和j无法用当前数字构造if(nums[i] j) dp[i][j] dp[i-1][j];// 选择是否将 nums[i] 放入背包dp[i][j]等于不放入背包和放入背包方式的总和else dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]];}}// 返回最终的结果即在考虑所有数字后构造和为add的方法数return dp[nums.size()-1][add];}
};
方法三01背包一维数组
具体细节就是初始化这里这个dp[0] 1相当于是按照结论推初始化因为按照二维的初始化方式是错误的最好还是去理解一下二维的吧……
class Solution {
public:int findTargetSumWays(vectorint nums, int target) { int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(target) sum) return 0; if ((target sum) % 2 1) return 0; int add (target sum) / 2; vectorint dp(add 1, 0); dp[0] 1;for (int i 0; i nums.size(); i) {for (int j add; j nums[i]; j--) { dp[j] dp[j - nums[i]];}}return dp[add]; }
};
