天津有做网站不错的吗,深圳罗湖商城网站建设,镇江seo方案,深圳网站设计教程LeetCode 1049 最后一块石头的重量 继续昨天没有详细说的01背包问题往下继续说。01背包问题是将dp从一维问题升维到二维之后会遇到的一类典型问题。dp数组自然而然地是一个横坐标表示物品序号-1#xff0c;纵坐标表示背包重量的二维数组。01背包由一个背包是否放该物品并比照后…LeetCode 1049 最后一块石头的重量 继续昨天没有详细说的01背包问题往下继续说。01背包问题是将dp从一维问题升维到二维之后会遇到的一类典型问题。dp数组自然而然地是一个横坐标表示物品序号-1纵坐标表示背包重量的二维数组。01背包由一个背包是否放该物品并比照后得到最大值来表示表示子问题和当前问题之间关系组成递推逻辑。递推过程中由于物品数组逐渐增加dp[i][j]在每一轮总是由dp[i-1][j]递推而来因此可以简化为用一维滚动数组来表示。但这样第二重循环中由于从前往后遍历dp[i][0]会被存放多次因此要从后往前遍历同时由于我们递推公式是一个将i号物品放入背包j减去其容量值将dp数组值加上物品value的过程这个过程逆序时前面的dp值也是正常放入了值不会被覆盖的。也因此我们可以采用一维数组来节省空间但要稍微调整内层循环遍历顺序。
初始化都默认为零即可。
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i 0; i stones.length; i) {sum stones[i];}int weight sum / 2;int[] dp new int[weight 1];for (int i 0; i stones.length; i) {for (int j weight; j stones[i]; j--) {dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return (sum - dp[weight] * 2);}
}
这道题转化为01背包问题的思路可以自行思考或者参照题解。
LeetCode 494 目标和 这一题其实还是可以转化为01背包问题。不过要加上目标数之后除以2如果加上之后为奇数或者小于0就直接返回0即可。否则我们直接用01背包模式求解即可。但是要注意由于我们求的是方法数所以要更改下递推公式为加上之前子问题的方法数。
代码如下
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}sum target;if (sum 0) return 0;if (sum % 2 1) return 0;sum / 2;int[] dp new int[sum 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j sum; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[sum];}
}
LeetCode 474 一和零 这题和上面差不多还是用的01背包问题而且要更明显一些。
代码如下
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[] n0 new int[strs.length];int[] n1 new int[strs.length];for (int i 0; i strs.length; i) {for (int j 0; j strs[i].length(); j) {if (strs[i].charAt(j) 0) n0[i];else n1[i];}}int[][] dp new int[m 1][n 1];for (int i 0; i strs.length; i) {for (int j m; j n0[i]; j--) {for (int k n; k n1[i]; k--) {dp[j][k] Math.max(dp[j][k], dp[j - n0[i]][k - n1[i]] 1);}}}return dp[m][n];}
}
