电路板东莞网站建设,青岛官网seo技术厂家,室内设计品牌,网站前台设计方案所用代码 java 最后一块石头的重量II LeetCode 1049
题目链接#xff1a;最后一块石头的重量II LeetCode 1049 - 中等
思路
无。 把石头分成重量总和近似两堆#xff0c;然后两堆石头相撞#xff0c;剩下的就是最小的石头。每个石头只能用一次#xff0c;01背包#xf… 所用代码 java 最后一块石头的重量II LeetCode 1049
题目链接最后一块石头的重量II LeetCode 1049 - 中等
思路
无。 把石头分成重量总和近似两堆然后两堆石头相撞剩下的就是最小的石头。每个石头只能用一次01背包
dp[j] 装满容量为 j 背包最大重量为dp[j]递推公式dp[j] max(dp[j], dp[j-stones[i]] stones[i])初始化dp[0] 0非零下标 0 背包容量由题意最多30块石头每个价值不超过100所以容量最大3000/2 1500即背包的容量可以定义为dp[1501]遍历方向0istones.length targetjstone[i]
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int stone : stones) {sum stone;}int target sum / 2; // 向下取整// leetcode最大3000int[] dp new int[1501];for (int i 0; i stones.length; i) {for (int j target; j stones[i]; j--) {dp[j] Math.max(dp[j], dp[j-stones[i]] stones[i]);}}// 由于target是向下取整的所以// 大的一堆sum - dp[target] 小的一堆 dp[target]return sum - dp[target] - dp[target];}
}二维数组
dp[i] [j] 放[0 - i]个石头在背包容量为j的情况下的最大重量初始化 dp[i] [0]背包为零重量为零 dp[0] [j] 下标为0的石头取决于背包大于等于stones[0]时可以装下
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int stone : stones) {sum stone;}int target sum / 2; // 向下取整// 初始化int[][] dp new int[stones.length][target 1];for (int j stones[0]; j target; j) {dp[0][j] stones[0];}// 外层 石头for (int i 1; i stones.length; i) {// 内层 背包for (int j 1; j target; j) {// 下一块石头装不下最大重量就是上一块石头的if (j stones[i]){dp[i][j] dp[i-1][j];}else {dp[i][j] Math.max(dp[i-1][j], dp[i-1][j-stones[i]] stones[i]);}}}
// System.out.println(dp[stones.length-1][target] dp[stones.length-1][target]);return sum - dp[stones.length-1][target] - dp[stones.length-1][target];}
}总结
同样这题分析看到这种两两成对的放东西而且一种物品只能放一个一般都是01背包问题分析清楚问题才好对症下药。
目标和 LeetCode 494
题目链接目标和 LeetCode 494 - 中等
思路
无。 分成两个集合一个集合放加法一个集合放减法
left right sum left - right target right sum - left left (target sum) / 2
集合里面挑出正数的集合等于(target sum) / 2剩下的就是负数的集合 不能整除就证明凑不成集合。
所以这题抽象成 背包容量为(target sum) / 2判断集合有多少种装满的情况
dp[j]装满背包容量为j的背包有dp[j]种方法递推公式dp[j] dp[j-nums[i]]初始化dp[0] 1 (空集也是一种方法) 非零下标初始为0遍历顺序物品0i nums.length 背包 bagSizejnums[i]
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int num : nums) sumnum;// 背包正数不能是小数或负数if ((target sum) % 2 1 || (target sum) / 2 0) return 0;int bagSize (target sum) / 2;// 初始化int[] dp new int[bagSize1];dp[0] 1;// 物品for (int i 0; i nums.length; i) {// 背包for (int j bagSize; j nums[i]; j--){dp[j] dp[j-nums[i]];
// System.out.print(dp[j] dp[j] \t);}
// System.out.println();}return dp[bagSize];}
}二维数组 dp[i] [j]从[0-i]挑选出的放数字恰好装满和为j的背包有dp[i] [j]种 递归公式dp[i] [j] dp[i-1] [j] dp[i-1] [j-nums[i]] 上一轮挑选出来的的和本轮未挑选dp[i-1] [j]上一轮加本轮挑选dp[i-1] [j-nums[i]] 初始化dp[0] [0] 1 dp[i] [0] 0 dp[0] [j] 装nums[0]只有j nums[0]这一种方法dp[0] [nums[0]] 1
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int num : nums) sumnum;// target的绝对值大于sum证明背包的数怎么都没法凑成sumif (Math.abs(target) sum) return 0;if ((target sum) % 2 1) return 0;int bagSize (target sum) / 2;// 初始化 - 新开一个物品维度以防止初始化0的情况int[][] dp new int[nums.length 1][bagSize 1];// 物品维度为0的物品不一定是0dp[0][0] 1;// 只放第0个物品只有背包容量为nums[0]刚好放下if (nums[0] bagSize) dp[1][nums[0]] 1;// 外层 物品for (int i 1; i nums.length 1; i) {// 内层 背包 // 从0开始遍历是因为我们只初始化了一个点, j0的情况没有初始化for (int j 0; j bagSize; j) {if (j nums[i-1]){// 不会放入背包dp[i][j] dp[i-1][j];}else {// 可以放入背包 i-1物品放入背包的数量 // i-1物品放入背包的数量再放入nums[i]的物品的最大数量dp[i][j] dp[i-1][j] dp[i-1][j-nums[i-1]];}
// System.out.print(\tdp[i][j] dp[i][j]);}
// System.out.println();}return dp[nums.length][bagSize];}
}总结
背包容量和价值用一个数表示的话使用一维数组更加方便只是我们在遍历的时候从后往前遍历行了以免前面的数据被覆盖。
一和零 LeetCode 474
题目链接一和零 LeetCode 474 - 中等
思路
无。 dp[i] [j]装满i个0j个1最多背dp[i] [j] 个物品递推公式dp[j] max(dp[j], dp[j-weight[i]] value[i]) m个0n个1dp[i] [j] max(dp[i] [j], dp[i-x] [j-y] 1)加1是物品的价值可看作1因为每次可以多放一个 初始化dp[0] [0] 0 非0下标也该初始化为0遍历顺序str 统计每个物品有多少个0 1 物品重量 im ix 背包容量这两个顺序可以颠倒jn jy
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m 1][n 1];// x表示0的个数y表示1的个数int x, y;// 遍历每一个物品for (String str : strs) {x 0;y 0;// 统计x和y的重量也就是出现的个数for (char c : str.toCharArray()){if (c 0) x;else y;}// 相当于滚动二维倒叙遍历for (int i m; i x; i--){ // 0的个数for (int j n; j y; j--){ // 1的个数dp[i][j] Math.max(dp[i][j], dp[i-x][j-y] 1);}}}return dp[m][n];}
}总结
本题元素就是物品每个物品只有一个所以dp[i-x] [j-y] 1 这里才是 1就是选了一个物品。
