网站专题页设计,北京网站制作费用,百度推广怎么开户,企业网站html百度云题意理解#xff1a; 有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。 思路转化#xff1a;我们可… 题意理解 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。 思路转化我们可以将题目转换为将石头分为大小相等差不多的两堆然后相互去撞击这样留下来的残余的石头就是可剩余的最小重量。 如何将石头分为大小相等的两堆呢。 targetsum(stones[])/2向上取整 ressum(stones[])-target 表示剩余的石头重量 此时再一次将题目转换为0-1背包问题 target表示背包重量stones表示物品stones[i]表示第i块石头的重量和价值。 此时问题转换为将物品装入大小为target的背包能获得的最大价值maxValue 此时石头被分为maxValue和sum-maxValue大小的两堆 res|sum-maxValue-maxValue|此时获得最小剩余大小的石头 解题思路 首先理解题意将其转换为一个背包问题使用动态规划的思路来求解。 动态规划五部曲 1dp[i][j]或dp[i]的含义 2递推公式 dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]values[i])或 dp[j]max(dp[j],dp[j-weight[i]]values[i]) 3根据题意初始化 4遍历求解:先遍历包还是先遍历物品 5打印——debug 1.动态规划二维dp数组
dp[i][j]表示下标[0,j]的元素任务放入大小为j的背包能获得的最大价值递推公式dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]values[i])初始化第一行第一列。遍历由于二维数组完整保留了两个维度所有信息所以先遍历背包还是先遍历物品都是可以的。
public int lastStoneWeightII(int[] stones) {int sum0;for(int num:stones)sumnum;int target(int)Math.ceil(sum/2);int[][] dpnew int[stones.length][target1];//初始化for(int[] tmp:dp) Arrays.fill(tmp,-1);for(int i0;istones.length;i) dp[i][0]0;for(int j1;jtarget;j){if(stones[0]j) dp[0][j]0;else dp[0][j]stones[0];}//遍历for(int i1;istones.length;i){for(int j1;jtarget;j){if(stones[i]j){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]);}}}return Math.abs(sum-dp[stones.length-1][target]*2);} 2.一维滚动数组——存储压缩
dp[j]表示装满大小为j的背包所能获得的最大价值。递推公式dp[j]max(dp[j],dp[j-weight[i]]values[i])初始化右边的值总是由最左边的值推导而来而最坐标的值dp[0]表示背包大小为0所能获得的最大价值所以有dp[0]0.将所有元素初始化为0遍历由于以为滚动数组是二维dp数组的动态行滚动更新所以遍历顺序总是先物品后背包。注意为了防止用同层修改过的值修改本行其他值导致物体重复放置故采用倒序遍历背包。 public int lastStoneWeightII2(int[] stones) {int sum0;for(int num:stones)sumnum;int target(int)Math.ceil(sum/2);int[] dpnew int[target1];//初始化Arrays.fill(dp,0);//遍历for(int i1;istones.length;i){for(int jtarget;j0;j--){if(stones[i]j){dp[j]dp[j];}else{dp[j]Math.max(dp[j],dp[j-stones[i]]stones[i]);}}}return Math.abs(sum-dp[target]*2);}
3.分析 时间复杂度O(n*target) 空间复杂度 二维O(n*target) 一维O(target) n是nums的长度target是sum(stones)/2的大小
