只做移动端的网站,wordpress移动端分享,深圳市住房和建设局网站公示,怎样建设美丽中国?题目来源#xff1a;https://leetcode.cn/problems/target-sum/description/ C题解#xff08;来源代码随想录#xff09;#xff1a;将该问题转为01背包问题。
假设加法的总和为x#xff0c;那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) target。x …题目来源https://leetcode.cn/problems/target-sum/description/ C题解来源代码随想录将该问题转为01背包问题。
假设加法的总和为x那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) target。x (target sum) / 2。此时问题就转化为装满容量为x的背包有几种方法。
确定dp数组以及下标的含义。1dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法。2也可以使用二维dp数组来求解本题dp[i][j]使用 下标为[0, i]的nums[i]能够凑满j包括j这么大容量的包有dp[i][j]种方法。确定递推公式。只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。dp数组如何初始化。dp[0] 1。确定遍历顺序。对于01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
// 代码随想录版本
class Solution {
public:int findTargetSumWays(vectorint nums, int S) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(S) sum) return 0; // 此时没有方案if ((S sum) % 2 1) return 0; // 此时没有方案int bagSize (S sum) / 2;vectorint dp(bagSize 1, 0);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j bagSize; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[bagSize];}
};// 一维数组版本
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {// left right sum;// left - right target;// left (sum target) / 2;// 01背包背包总量left价值和为j的个数为dp[j]// dp[j] dp[j]dp[j-nums[i]]int len nums.size();int sum 0;for(int i 0; i len; i) {sum sum nums[i];}if(sum target || target -sum) return 0;else if((sum - target) % 2 1) return 0;int left (sum target) / 2;vectorint dp(left1, 0);dp[0] 1; // 初始化if(nums[0] left) dp[nums[0]]; // 考虑left nums[0] 0的情况for(int i 1; i len; i) {for(int j left; j nums[i]; j--) {dp[j] dp[j] dp[j-nums[i]];}}return dp[left];}
};
// 二维数组版本
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {// left right sum;// left - right target;// left (sum target) / 2;// 01背包背包总量left在0-i个物品中价值和为j的个数为dp[i][j]// dp[i][j] dp[i-1][j]dp[i-1][j-nums[i]]int len nums.size();int sum 0;for(int i 0; i len; i) {sum sum nums[i];}if(sum target || target -sum) return 0;else if((sum - target) % 2 1) return 0;int left (sum target) / 2;vectorvectorint dp(len, vectorint(left1, 0));dp[0][0] 1; // 初始化if(nums[0] left) dp[0][nums[0]]; // 考虑left nums[0] 0的情况for(int i 1; i len; i) {for(int j 0; j left; j) {if(j nums[i]) dp[i][j] dp[i-1][j];else dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]];}}return dp[len-1][left];}
};
