最后一块石头的重量 Posted on 2021-09-05 00:00:00 2021-09-05 00:00:00 by Author 摘要 石头大作战，给定一些石头，这些石头相互碰撞，最后只有一块石头能够胜出，你能找到最后胜利石头的重量是多少吗 ## 最后一块石头的重量 1. 题目描述 - 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： - 如果 x == y，那么两块石头都会被完全粉碎； - 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 - 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 - **提示：** - `1 <= stones.length <= 30` - `1 <= stones[i] <= 100` 2. 示例描述 - 示例一 ```java 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。 ``` - 示例二 ```java 输入：stones = [31,26,33,21,40] 输出：5 ``` 3. 解题思路 - 首先对于本题来说和[分割等和子集](http://www.geticsen.cn/view/articles/detail/971f9d1f-b5b8-4b07-acf7-4a6006864d82)这道题比较相似，其实可以套用，上一道题的思想是看所给的数组是不是可以平分 ，而本题也可以把按照所给石头总重量平分为两堆，这两堆石头都是所给石头数组组成的，假如这两堆石头重量相等，那么这两堆石头相互粉碎，最后所剩的体积也就为0，如果这两对石头体积不相等，它两之间差值越小那么最后相互粉碎所剩的体积也就越小。所以这里可以这样想，先算出所给数组石头的总重量，得到石头一半的重量target是多少，然后从所给的石头数组中去挑选几个石头，使其总重量等于或者接近于target,那么另一对石头的总重量也就接近于target，那么两堆石头重量之差也就越小。这就间接解决了这道题 - 具体实现的方式与[分割等和子集](http://www.geticsen.cn/view/articles/detail/971f9d1f-b5b8-4b07-acf7-4a6006864d82)相似，然后思想也相似，以下的代码每一步都有具体的说明，结合前一道题与这道题一起思考，就会明白这种类型题目的相似之处了。具体实现方式如代码示例。 4. 代码示例 ```java public int lastStoneWeightII(int[] stones) { //所给石头数组总和重量 int sum = 0; for (int i = 0; i < stones.length; i++) { sum += stones[i]; } //把石头分为两堆， //其中一堆看所给的石头最多能够组成多少重量 int target = sum / 2; //定义一个dp数组 //长度为什么是target+1,前面知道了所给石头数组的总重量，如果石头相互粉碎 //那么当两堆石头重量相等时，他们相互粉碎，所剩的重量最少， //所以这里只用算一堆石头，另一堆石头就用总和减去这堆石头，就是最后所剩的重量了。 int dp[] = new int[target + 1]; //这里dp数组的含义是:dp[j]:对于每一个j来说，我们可以把j当作一个背包，这个背包最大可以装纳体积为j的石头 //那么所给石头数组中，挑选几块使得背包j，里面装的石头体积最大(前提是装的石头体积和不能大于背包容量，也就是j) //那么dp[target]里面就是放的target容量的背包，里面装的最大体积是多少，那么另一堆石头重量就拿总重量sum减去这堆石头最大的重量即可， //他们的差就是所剩最小的体积了。 for (int i = 0; i < stones.length; i++) {//每个石头都去放入不同的背包中， for (int j = target; j >= stones[i]; j--) {//每一个容量为j的背包都去放这个石头，看每个背包所容纳最大体积是多少 //这里递推公式含义是:当一个石头来的时候，如果该石头能够放入背包中，那么我们就先让背包腾出该石头重量的体积出来 //这里就是[dp[j-stones[i]],然后得到容量为j-stones[i]背包所能容纳最大石头体积是多少， //此时已经给该石头腾出一个地方了，那么现在把该石头方法背包容量为j的背包中，看此时背包j容量是多少， // 如果把该石头放进去，容量大于之前的背包的容量，那么该石头可以放入该背包中了， //当所有石头都遍历完成，就dp数组就存储了每个不同容量背包所容纳的最大的石头体积了。 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); } } //返回最后所剩未能粉碎的石头的体积 //其中sum-dp[target]代表的是一堆石头的重量，最后一个dp[target]代表的是另一堆石头的重量 //两堆石头重量相减就知道最后所剩最小的重量了。 return sum - dp[target] - dp[target]; } ```
{{ item.content }}
{{ child.content }}