恋爱网站建设,网页建站,太原手手工网站建设公司,把微信小程序做网站在本题中#xff0c;我们可以知道#xff0c;是要求最后石头返还的重量#xff0c;也就是#xff0c;将整个数组分割成两个子集#xff0c;求让两个子集的差值最小。这和上一道分割整数集类似#xff0c;只是需要我们返回差值。所以我们采用动态规划01背包来做#xff0… 在本题中我们可以知道是要求最后石头返还的重量也就是将整个数组分割成两个子集求让两个子集的差值最小。这和上一道分割整数集类似只是需要我们返回差值。所以我们采用动态规划01背包来做最后将分割的两个子集的差值返回即可。
首先我们明确dp数组的含义就是dp[j]代表容量为j的背包的价值为dp[j]。
递推公式也类似上一道题采用一维01背包递推公式即可 dp[j] Math.max(dp[j]dp[j-weight[i]]values[i])。
初始化dp[0] 0因为容量为0价值肯定是0其他位置依旧取最大值可以覆盖即可那么就取0就可以了。
遍历顺序01背包一维数组遍历顺序应该先遍历物品再遍历背包背包并且要从大往小遍历。
打印数组
我们最后返回的应该是两个部分的差值也就是dp[target]和sum-dp[target]这两部分的差值sum-dp[target]一定比dp[target]大因为dp[target]是sum/2得到的target除法是向下取整的。
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i : stones) {sum i;}int target sum 1;//相当于sum/2因为除法是向下取整这样比如5/2结果应该是2那么剩下的部分是5-5/23则两部分差值就是3-21//初始化dp数组int[] dp new int[target 1];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]);}}return sum - 2 * dp[target];}
}
