深圳html5网站制作,招聘网站开发的要求,wordpress+播放列表,南昌哪里学做网站本题链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目#xff1a;
思路#xff1a; 根据这道题#xff0c;可以通过暴力的方法进行取 号或者 - 号 两个操作#xff0c;通过当刚好得到 target 的时候 答案 1#xff0c;但是通过长度是 20 #xff0c;操…本题链接. - 力扣LeetCode
题目
思路 根据这道题可以通过暴力的方法进行取 号或者 - 号 两个操作通过当刚好得到 target 的时候 答案 1但是通过长度是 20 操作状态为 2个随后的回溯暴力递归最坏的情况时间复杂度大约是 20^20^2 ,肯定会TLE了。 这时候就用到了动态规划dp这里我们可以知道有两个操作 -我们分成两个子集一些放正号子集 left另一些放负号子集 righ。
最后得到 left righ sum 其中 sum 为整个 nums 数组的总和
然后将两个子集合并 left - righ target
根据这两个式子我们可以推导出 left (sum target) / 2 这时候我们又可以将其看作为 背包问题了根据题目意思要求的是能够凑成 target的方法有多少种相当于背包问题中能够刚好装满给背包容量的方案数是多少一样的。
只是这里需要计算背包容量 v 为 left
代码详解如下
inline int findTargetSumWays(vectorint nums, int target)
{int sum 0; // 计算 nums 数组的总和for(int i:nums) sum i;// 分成两个子集 一个是正号的子集 left , 一个是 负号的子集 righ// left righ sum// left - righ target// left (sum target) / 2// 令 left 作为 背包容量问刚好凑够 left 的子集有多少种方法// 其中 当 (sum target) 不能被 2 整除 或者 当全部为 号 或者 -号 的sum 小于 target说明根本凑不齐int v (sum target) / 2;if(v * 2 ! (sum target) || abs(target) sum) return 0;// dp[i] 中 i 含义为 装满 容量 i dp[i] 含义为 装满 容量 i 的方法有多少种 int n nums.size();vectorintdp(n 1000,0);/* 递推公式 dp[i - num[i]] dp[i] 即 有 dp[target - num[i]]种方法 凑成 dp[target] 假设 num[i] i target 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[5] 中方法总共有 dp[0] dp[1] dp[2] dp[3] dp[4]最后公式为 dp[i] dp[i - nums[i]]*/// dp 初始化 0 凑成 0 的方法只有一种dp[0] 1;for(int i 0;i n;i){for(int j v;j nums[i];--j){dp[j] dp[j - nums[i]];}}return dp[v];
}
最后提交
