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
函数用于计算两个整数中的较大值。
注意:由于题目要求粉碎的重量差最小,因此需要将石头分为两组,使它们的重量之差最小。因此在计算完一组石头的最大重量后,还需要用总重量减去两堆石子的总重量之差,以得到另一组石头的重量。
时间复杂度:该算法使用了动态规划方法,在遍历石头和目标重量的过程中,对于每个子问题都需要计算一次最大重量,因此时间复杂度为 ,其中 是石头数量, 是目标重量的一半。
空间复杂度:在使用动态规划求解最大重量的过程中,需要使用一个二维数组 dp
来保存所有子问题的计算结果。因此空间复杂度为 。但由于每次迭代只需要使用到上一次迭代的结果,因此可以使用滚动数组将空间复杂度优化到 。
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
}
标签:stones,重量,石头,总重量,sum,dp
From: https://blog.51cto.com/u_14891145/6210676