2023-04-20：有一堆石头，用整数数组 stones 表示其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎假设石头的重量分别为 x 和

2023-04-20
北京
本文字数：1793 字
阅读完需：约 6 分钟

2023-04-20：有一堆石头，用整数数组 stones 表示其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎假设石头的重量分别为 x 和 y，且 x <= y 那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

答案 2023-04-20：

算法流程：

遍历一遍所有石头，计算石头总重量 sum；
计算目标重量 target = sum / 2；
使用动态规划求解在限制条件下可以得到的最大重量；
返回石头总重量减去两堆石子的总重量之差，即为最小重量差。

动态规划过程：

定义状态：设 dp[i][j] 表示前 i 个石头在限制条件下可以得到的最大重量；
初始化状态：dp[0][j] = 0，表示前 0 个石头在限制条件下无法得到任何重量；dp[i][0] = 0，表示在不限制目标重量的情况下无法得到任何重量；
状态转移方程：对于第 i 个石头，有两种选择：取或不取。若不取，则当前石头对总重量贡献为 0，即 dp[i][j] = dp[i-1][j]。若取，则当前石头会对总重量产生贡献，贡献值为当前石头重量 stones[i-1] 加上前 i-1 个石头在目标重量为 j - stones[i-1] 下可以得到的最大重量 dp[i-1][j-stones[i-1]]，即 dp[i][j] = dp[i-1][j-stones[i-1]] + stones[i-1]。因此可以得到状态转移方程：

   dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1])

复制代码

最终结果：返回 sum - 2 * dp[n][target]。

其中，max 函数用于计算两个整数中的较大值。

注意：由于题目要求粉碎的重量差最小，因此需要将石头分为两组，使它们的重量之差最小。因此在计算完一组石头的最大重量后，还需要用总重量减去两堆石子的总重量之差，以得到另一组石头的重量。

时间复杂度：该算法使用了动态规划方法，在遍历石头和目标重量的过程中，对于每个子问题都需要计算一次最大重量，因此时间复杂度为 $O (n \times half)$ ，其中 $n$ 是石头数量， $half$ 是目标重量的一半。

空间复杂度：在使用动态规划求解最大重量的过程中，需要使用一个二维数组 dp 来保存所有子问题的计算结果。因此空间复杂度为 $O (n \times half)$ 。但由于每次迭代只需要使用到上一次迭代的结果，因此可以使用滚动数组将空间复杂度优化到 $O (half)$ 。

go 完整代码如下：

package main
import "fmt"
func lastStoneWeightII(stones []int) int {  n := len(stones)  sum := 0  for _, num := range stones {    sum += num  }  half := sum / 2  dp := make([][]int, n+1)  for i := range dp {    dp[i] = make([]int, half+1)  }  for i := n - 1; i >= 0; i-- {    for rest := 0; rest <= half; rest++ {      p1 := dp[i+1][rest]      p2 := 0      if stones[i] <= rest {        p2 = stones[i] + dp[i+1][rest-stones[i]]      }      dp[i][rest] = max(p1, p2)    }  }  return sum - dp[0][half]*2}
func max(x, y int) int {  if x > y {    return x  }  return y}
func main() {  stones := []int{2, 7, 4, 1, 8, 1}  fmt.Println(lastStoneWeightII(stones)) // expected output: 1
  stones = []int{31, 26, 33, 21, 40}  fmt.Println(lastStoneWeightII(stones)) // expected output: 5}

复制代码

rust 代码如下：

fn last_stone_weight_ii(arr: Vec<i32>) -> i32 {    let n = arr.len();    let sum = arr.iter().sum::<i32>();    let half = sum / 2;    let mut dp = vec![vec![0; half as usize + 1]; n + 1];    for i in (0..n).rev() {        for rest in 0..=half {            let p1 = dp[i + 1][rest as usize];            let mut p2 = 0;            if arr[i] <= rest as i32 {                p2 = arr[i] + dp[i + 1][(rest - arr[i]) as usize];            }            dp[i][rest as usize] = p1.max(p2);        }    }    (sum - dp[0][half as usize] * 2) as i32}
fn main() {    let stones = vec![2, 7, 4, 1, 8, 1];    let ans = last_stone_weight_ii(stones);    println!("{}", ans); // 输出 1
    let stones = vec![31, 26, 33, 21, 40];    let ans = last_stone_weight_ii(stones);    println!("{}", ans); // 输出 5}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/bd36c0aafda1d8a2118ef3121】。

福大大架构师每日一题

关注

公众号：福大大架构师每日一题 2021-02-15 加入

公众号：福大大架构师每日一题

发布

暂无评论

创作场景

2023-04-20：有一堆石头，用整数数组 stones 表示 其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎 假设石头的重量分别为 x 和

go 完整代码如下：

rust 代码如下：

福大大架构师每日一题

评论

2023-04-20：有一堆石头，用整数数组 stones 表示其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎假设石头的重量分别为 x 和