官方网站建设 都来磐石网络,马鞍山做网站公司排名,公司网站开发有哪些,人社部门网站建设1. 回溯算法
这题和之前做的那些排列、组合的回溯稍微有些不同#xff0c;你不需要每次选数据时都是for遍历去选择#xff0c;很明显这是顺序选择的 比如 数组[0,1]#xff0c;target1#xff1b; 递归数组#xff0c;每个元素都 或者 - #xff0c;然后取最后结果为0…
1. 回溯算法
这题和之前做的那些排列、组合的回溯稍微有些不同你不需要每次选数据时都是for遍历去选择很明显这是顺序选择的 比如 数组[0,1]target1 递归数组每个元素都 或者 - 然后取最后结果为0的即可
class Solution {public int findTargetSumWays(int[] nums, int target) {find(0,nums,target);return count;}private void find(int begin,int[] nums,int target){// 如果减完了结束if(begin nums.length){if(target 0){count;}return;}target-nums[begin];find(begin1,nums,target);targetnums[begin];targetnums[begin];find(begin1,nums,target);target-nums[begin]; }private int count0;
}2. 动态规划
这其实可以抽象为0/1背包问题。 数组中的元素要么是前面要么是前面-问计算结果为target的方案有多少种。 计算结果为0即我们把前面为的元素放在一个集合A中前面为-的元素放在一个集合B中二者之差为target即可。 我们如果知道了集合A那么集合B自然就是数组中剩余元素组成。
可以列个简单的数学公式假设A集合元素的和为left,B元素和为right数组总和为sum left right sum; left - right target; 二者一相加可以得到 left(sumtarget)/2; 由于都是正整数left如果不是正整数说明无解即没有这种方案。
思路成功转换为背包容量为left在数组中找出和刚好为left的方案并记录方案的最大数。
确定dp[i][j]
即dp[i][j] 在数组中下标为0i的元素中任选和刚好为j的方案数量 确定递推公式 如果第i个元素不选那方案数量和dp[i-1][j]的一样 dp[i][j] dp[i-1][j] 如果选了第i个元素那方案就不仅仅从i-1个元素选出和为j的从i-1个元素选出和为j-nums[i]的也可以两种方案数相加。 dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]] 如何初始化 dp[0][0]1 我可以都不选那方案数就是1 初始化第一行 dp[0][nums[0]]1; 题目中提示给出nums[i]范围是可能为0所以如果nums[0]0,那就是dp[0][0]中都不选的方案中再添加一种选择元素0那就是两个方案了 重点细节卡了我一个上午 确定遍历顺序 先数组元素再背包容量 模拟推导
class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length 1){return target nums[0]?1:target 0-nums[0]?1:0;}// 把集合分成前面放的正集合和前面放-的负集合.正集合的和为left负集合的和为right// leftrightsum left-righttarget left (targetsum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时如果left不为整数说明不行返回0// dp[i][j] 在下标0为i的元素中填满背包容量为j有多少种方案// dp[i][j] dp[i-1][j] 如果不装i// dp[i][j] Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum0;for(int i:nums){sum i;}if((targetsum)%2 ! 0 ){return 0;}if(target sum || target -sum){return 0;}int num (targetsum)/2;num num 0?-num:num;int[][] dp new int[nums.length][num1];// 当容量为0的时候都不选就是一种方案for(int i0;inums.length;i){dp[i][0]1;}// 遍历第一行dp[0][nums[0]]1 因为可能第一行中nums[0]0,此时dp[0][0]其实已经初始化为1了但是dp[0][0]其实有两个方案的一个是都不选一个是选了0这个细节决定了我们后续的遍历从第二行开始是否成功if(nums[0]num1){dp[0][nums[0]]1;}for(int i1;inums.length;i){for(int j0;jnum1;j){dp[i][j] dp[i-1][j];if(jnums[i]){dp[i][j] dp[i-1][j-nums[i]] dp[i-1][j]; } }}return dp[nums.length-1][num];}
}优化成一维的
class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length 1){return target nums[0]?1:target 0-nums[0]?1:0;}// 把集合分成前面放的正集合和前面放-的负集合.正集合的和为left负集合的和为right// leftrightsum left-righttarget left (targetsum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时如果left不为整数说明不行返回0// dp[i][j] 在下标0为i的元素中填满背包容量为j有多少种方案// dp[i][j] dp[i-1][j] 如果不装i// dp[i][j] Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum0;for(int i:nums){sum i;}if((targetsum)%2 ! 0 ){return 0;}if(target sum || target -sum){return 0;}int num (targetsum)/2;num num 0?-num:num;int[]dp new int[num1];// 当容量为0的时候都不选就是一种方案dp[0]1;// 遍历第一行if(nums[0]num1){dp[nums[0]]1;}for(int i1;inums.length;i){for(int jnum;jnums[i];j--){dp[j] dp[j-nums[i]]; }}return dp[num];}
}这道题很经典建议过段时间重复刷
