网站原则,四川高速公路建设集团网站,如何用php做网站管理系统,广西建设厅网站招 标 信 息题目描述
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘’ 或 ‘-’ #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a;
例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 ‘’ #xff0c;在 1 之…题目描述
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 代码 回溯
class Solution {
public:int count 0;void backTracking(const vectorint nums, const int target, int index, int sum) {if (index nums.size()) {if(sumtarget)count;}else {backTracking(nums, target, index 1, sum nums[index]);backTracking(nums, target, index 1, sum - nums[index]);}}int findTargetSumWays(vectorint nums, int target) {backTracking(nums, target, 0, 0);return count;}
};动态规划
/*left是正数集合right是负数集合left - right targetleft right sumleft (sumtarget) / 2right (sum-target) / 2如果不能整除 直接return 0;将left (sumtarget)/2 看做是背包的容量看有多少种方法能将背包装满dp[j] 装满容量为j的背包有dp[j]种方法递推公式已有 可以凑成的数量以5为例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[j]dp[j-nums[i]]初始化dp[0] 1;遍历顺序for(int i0;inums.size();i)for(int j left;jnums[i];j--)dp[j] dp[j-nums[i]]
*/class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int a : nums) sum a;if (abs(target)sum || (sum target) % 2 ! 0) return 0;int left (sum target) / 2;vectorint dp(left 1, 0);dp[0] 1;for(int i0;inums.size();i)for (int j left; j nums[i]; j--) {dp[j] dp[j - nums[i]];}return dp[left];}
};
