网站开发女生,google站长工具,网站开发技术应用领域,共享设计平台文章目录题目描述思路 代码1. 动态规划 O(n2n^2n2)、O(n2n^2n2)#xff08;最方便理解#xff0c;初版#xff09;2. 转换成 01 背包问题 O(n2n^2n2)、O(nnn)二刷离谱#xff01;添加了测试用例#xff0c;上面的代码需要添加负数条件了#xff08;见下面的代…
文章目录题目描述思路 代码1. 动态规划 O(n2n^2n2)、O(n2n^2n2)最方便理解初版2. 转换成 01 背包问题 O(n2n^2n2)、O(nnn)二刷离谱添加了测试用例上面的代码需要添加负数条件了见下面的代码打卡第十五天继续加油 题目描述
和上一道分割等和子集的做法很像这里代码迭代了很多次但是时间复杂度是一样的只是空间复杂度、耗时不断优化。
思路 代码
1. 动态规划 O(n2n^2n2)、O(n2n^2n2)最方便理解初版
dp[i][j]下标[0 ~ i]构成的数集能得到 j - sum 的情况种数因为nums[ ]可构成元素范围为[-sum, sum]因此开出[2 * sum 1]的列数组。 其中[0] 代表 -sum[2 * sum] 代表 [sum]以此类推。注意初始化时nums[0] 可能等于 -nums[0]因此要用到 而非 。状态转移对于当前的 j分成 nums[i]和-nums[i]的情况对上一行的值进行选取即可。缺陷空间复杂度不方便通过滚动数组的方式进行优化因为状态转移方程的过程中不但用到了前面的元素还用到的后面的元素。解决方法转换成01背包问题
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int temp : nums) {sum temp;}// 全正 or 全负不在范围的情况if(sum target || -sum target) {return 0;}// dp[i][j]下标[0 ~ i]构成的数集能得到 j - sum 的情况种数int top 2 * sum 1;int[][] dp new int[nums.length][top];// 初始化只取第一个元素只能给 nums[0] 和 -nums[0] 带来 1 个种数dp[0][sum nums[0]] 1;// 注意存在 nums[0] -nums[0] 的情况因此这边要用 dp[0][sum - nums[0]] 1;// 状态转移for(int i 1; i nums.length; i) {for(int j 0; j top; j) {// Case 1第 i 个元素取 if(j nums[i]) {dp[i][j] dp[i - 1][j - nums[i]];}// Case 2: 第 i 个元素取 -if(j nums[i] top) {dp[i][j] dp[i - 1][j nums[i]];}}}return dp[nums.length - 1][target sum];}
}2. 转换成 01 背包问题 O(n2n^2n2)、O(nnn)
实际上题目可以这样转换成01背包问题把 - 当成 0不选把 当成 1选。原本的(-nums) (nums) target表达式左边和右边都加上 sum就转换成 0 2 * (nums) sum target方便起见我们可以再进行除2操作变成 nums (sum target) / 2。注意由此可推出如果(sum target) 为奇数说明不存在对应的 nums 序列也就是不可取。接下来就可以正常地进行 01背包 的动态规划了滚动数组逆序现在没有减法的情况下可以保证无后效性
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int temp : nums) {sum temp;}// 不在范围的情况 奇数无法匹配到选取方式可证if(sum target || (sum target) % 2 1) {return 0;}// 转换成 01背包-号转成不取号转成取两倍// 实际上只要考虑到 target sum 即可后面的和结果无关int top (sum target) / 2 1;// dp[i][j]下标[0 ~ i]构成的数集能得到 j - sum 的情况种数int[] dp new int[top];// 初始化第一个元素不取只能给 0 带来 1 个种数dp[0] 1;// 状态转移for(int i 0; i nums.length; i) {for(int j top - 1; j nums[i]; j--) {// Case 1取第 i 个元素dp[j] dp[j - nums[i]];// Case 2: 不取第 i 个元素一维情况下相当于不用考虑}}return dp[top - 1];}
}来个无注释版代码吧方便直接看代码
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int temp : nums) {sum temp;}if(sum target || (sum target) % 2 1) {return 0;}int top (sum target) / 2 1;int[] dp new int[top];dp[0] 1;for(int i 0; i nums.length; i) {for(int j top - 1; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[top - 1];}
}二刷
离谱添加了测试用例上面的代码需要添加负数条件了见下面的代码
class Solution {public int findTargetSumWays(int[] nums, int target) {// 转换成背包取两次-不取。target 相当于加了一次 sumfor(int temp : nums) {target temp;}// 偶数之和不能为奇数 || 非负数之和不能为负if(target % 2 1 || target 0) {return 0;}target / 2;int[] dp new int[target 1];// 边界处理0的组合法有一个都不取dp[0] 1;for(int i 0; i nums.length; i) {for(int j target; j nums[i]; j--) {// 相当于这一轮的结果 上一轮的结果 这一轮的添加dp[j] dp[j - nums[i]];}}return dp[target];}
}无注释版11行有效代码
class Solution {public int findTargetSumWays(int[] nums, int target) {for(int temp : nums) {target temp;}if(target % 2 1 || target 0) {return 0;}target / 2;int[] dp new int[target 1];dp[0] 1;for(int i 0; i nums.length; i) {for(int j target; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[target];}
}
