像聚美网站建设费用,南昌seo计费管理,可信赖的购物网站建设,餐馆效果图网站题意理解#xff1a; 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a; 例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 #xff0c;在 1 之前添… 题意理解 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式 例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 简单来说就是在元素前面加‘’或‘-’使其结果值为target。 可以将其思路转换为将数组元素分为两部分其差为target。 则有part1-part2targetpart1part2sum part1(sumtarget)/2 固有我们需要将数组元素分为两部分一部分较大的为part1(sumtarget)/2,较小的部分为part2(sum-target)/2。 此时我们再次转变思路将其构造成0-1背包问题 背包大小为m(sumtarget)/2 物品为[0,n]的元素其价值和重量都是nums[] 接下来使用动态规划中的0-1背包思路解决问题。 解题思路 首先理解题意将其转换为一个背包问题使用动态规划的思路来求解。 动态规划五部曲 1dp[i][j]或dp[i]的含义 2递推公式 3根据题意初始化 4遍历求解:先遍历包还是先遍历物品 5打印——debug 1.动态规划二维dp数组
dp[i][j]表示[0,i]的元素装满大小为j的背包有多少种方法。递推公式dp[i][j]dp[i-1][j]dp[i-1][j-nums[i]] 当当前物品大于当前背包的大小时放满大小为j的背包的方法数仍就为dp[i-1][j].当当前物品小于等于当前背包的大小时放满大小为j的背包的方法数dp[i-1][j]dp[i-1][j-nums[i]]其中dp[i-1][j-nums[i]]是增加了物品nums[i]后增加的方法数。初始化初始化第一列其中特别的放满背包大小0 有多少种方法——要么什么也不放要么放入大小为0的物品。初始化时要根据问题具体分析。遍历由于二维数组保留了两个维度所有值所以先便利包还是先遍历物品都可以
public int findTargetSumWays(int[] nums, int target) {int sum0;for(int num:nums){sumnum;}//是否能按照需求分成两部分if((sumtarget)%2!0) return 0;if((sum-target)%2!0) return 0;//把所有值当作整数分成两部分一正一负即可所以如果target总保持为正数if(target0) target-target;int size (int)Math.ceil((float)(sumtarget)/2);int dp[][]new int[nums.length][size1];//初始化for(int[] temp:dp) Arrays.fill(temp,0);int countZero0;for(int i0;inums.length;i){if(nums[i]0) countZero;dp[i][0]countZero1;}for(int j1;jsize;j){if(nums[0]j) dp[0][j]1;else dp[0][j]0;}//遍历顺序for(int i1;i nums.length;i){for(int j0;jsize;j){if(jnums[i]){dp[i][j]dp[i-1][j];}else{dp[i][j]dp[i-1][j]dp[i-1][j - nums[i]];}}}return dp[nums.length-1][size];} 2.一维滚动数组——存储压缩
dp[j]表示装满大小为j的背包有多少种方式。递推公式dp[j]max(dp[j],dp[j-weight[i]]values[i])初始化右边的值总是由最左边的值推导而来,dp[0]表示使背包价值为0有多少种放置方法——要么什么也不放要么放大小为0的物品。遍历由于以为滚动数组是二维dp数组的动态行滚动更新所以遍历顺序总是先物品后背包。注意为了防止用同层修改过的值修改本行其他值导致物体重复放置故采用倒序遍历背包。 public int findTargetSumWays(int[] nums, int target) {int sum0;for(int num:nums) sumnum;if((sumtarget)%2!0) return 0;if((sum-target)%2!0) return 0;if(target0) target-target;int size (int)Math.ceil((float)(sumtarget)/2);int dp[]new int[size1];//初始化Arrays.fill(dp,0);dp[0]1;//遍历顺序for(int i0;i nums.length;i){for(int jsize;jnums[i];j--){dp[j] dp[j - nums[i]];}}return dp[size];} 3.分析 时间复杂度O() 空间复杂度 二维O(n*size) 一维O(size)
