Input: stones = [3,2,4,1],K = 2 Output: 20 Explanation: We start with [3,1]. We merge [3,2] for a cost of 5,and we are left with [5,1]. We merge [4,1] for a cost of 5,5]. We merge [5,5] for a cost of 10,and we are left with [10]. The total cost was 20,and this is the minimum possible. 

Input: stones = [3,K = 3 Output: -1 Explanation: After any merge operation,there are 2 piles left,and we can‘t merge anymore. So the task is impossible. 

Input: stones = [3,5,1,6],K = 3 Output: 25 Explanation: We start with [3,6]. We merge [5,2] for a cost of 8,and we are left with [3,8,6]. We merge [3,6] for a cost of 17,and we are left with [17]. The total cost was 25,and this is the minimum possible. 

输入：stones = [3,K = 2
输出：20
解释：
从 [3,1] 开始。
合并 [3,2]，成本为 5，剩下 [5,1]。
合并 [4,1]，成本为 5，剩下 [5,5]。
合并 [5,5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。

输入：stones = [3,K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.

输入：stones = [3,K = 3
输出：25
解释：
从 [3,6] 开始。
合并 [5,2]，成本为 8，剩下 [3,6]。
合并 [3,6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。 

 1 class Solution {
 2     func mergeStones(_ stones: [Int],_ K: Int) -> Int {
 3         var n:Int = stones.count
 4         var pre:[Int] = [Int](repeating:0,count:n + 1)
 5         for i in 1...n
 6         {
 7             pre[i] = pre[i - 1] + stones[i - 1]
 8         }
 9         var inf:Int = 1000000000
10         var dp:[[[Int]]] = [[[Int]]](repeating:[[Int]](repeating:[Int](repeating:inf,count:205),count:205)
11         for i in 1...n
12         {
13             dp[i][i][1] = 0
14         }
15         for len in 1...n
16         {
17             var i:Int = 1
18             while(i + len - 1 <= n)
19             {
20                 var j:Int = i + len - 1
21                 if len >= 2
22                 {
23                     for k in 2...len
24                     {
25                         var t:Int = i
26                         while(t + 1 <= j)
27                         {
28                             dp[i][j][k] = min(dp[i][j][k],dp[i][t][k - 1] + dp[t + 1][j][1])
29                             t += 1
30                         }
31                     }
32                 }                
33                 dp[i][j][1] = min(dp[i][j][1],dp[i][j][K] + pre[j] - pre[i - 1])                
34                 i += 1
35             }
36         }
37         if dp[1][n][1] >= inf
38         {
39             return -1
40         }
41         return dp[1][n][1]
42     }
43 }

本文分享自微信公众号 - 福大大架构师每日一题（gh_bbe96e5def84）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与 “OSC 源创计划”，欢迎正在阅读的你也加入，一起分享。

2021-08-24：合并石头的最低成本。有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的

2021-08-24：合并石头的最低成本。有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

福大大 答案2021-08-24：

动态规划。
时间复杂度：O(N^2K)。
空间复杂度：O(N^2K)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
   
    arr := []int{
   3, 2, 4, 1}
    k := 2
    ret := mergeStones1(arr, k)
    fmt.Println(ret)
    fmt.Println("--------")
    ret = mergeStones2(arr, k)
    fmt.Println(ret)
}

func mergeStones1(stones []int, K int) int {
   
    n := len(stones)
    if (n-1)%(K-1) > 0 {
   
        return -1
    }
    presum := make([]int, n+1)
    for i := 0; i < n; i++ {
   
        presum[i+1] = presum[i] + stones[i]
    }
    return process1(0, n-1, 1, stones, K, presum)
}

// part >= 1
// arr[L..R] 一定要弄出part份，返回最低代价
// arr、K、presum（前缀累加和数组，求i..j的累加和，就是O(1)了）
func process1(L int, R int, P int, arr []int, K int, presum []int) int {
   
    if L == R {
    // arr[L..R]
        return twoSelectOne(P == 1, 0, -1)
    }
    // L ... R 不只一个数
    if P == 1 {
   
        next := process1(L, R, K, arr, K, presum)
        if next == -1 {
   
            return -1
        } else {
   
            return next + presum[R+1] - presum[L]
        }
    } else {
    // P > 1
        ans := math.MaxInt64
        // L...mid是第1块，剩下的是part-1块
        for mid := L; mid < R; mid += K - 1 {
   
            // L..mid(一份) mid+1...R(part - 1)
            next1 := process1(L, mid, 1, arr, K, presum)
            next2 := process1(mid+1, R, P-1, arr, K, presum)
            if next1 != -1 && next2 != -1 {
   
                ans = getMin(ans, next1+next2)
            }
        }
        return ans
    }
}

func twoSelectOne(c bool, a int, b int) int {
   
    if c {
   
        return a
    } else {
   
        return b
    }
}

func getMin(a int, b int) int {
   
    if a < b {
   
        return a
    } else {
   
        return b
    }
}

func mergeStones2(stones []int, K int) int {
   
    n := len(stones)
    if (n-1)%(K-1) > 0 {
    // n个数，到底能不能K个相邻的数合并，最终变成1个数！
        return -1
    }
    presum := make([]int, n+1)
    for i := 0; i < n; i++ {
   
        presum[i+1] = presum[i] + stones[i]
    }
    dp := make([][][]int, n)
    for i := 0; i < n; i++ {
   
        dp[i] = make([][]int, n)
        for j := 0; j < n; j++ {
   
            dp[i][j] = make([]int, K+1)
        }
    }
    return process2(0, n-1, 1, stones, K, presum, dp)
}

func process2(L int, R int, P int, arr []int, K int, presum []int, dp [][][]int) int {
   
    if dp[L][R][P] != 0 {
   
        return dp[L][R][P]
    }
    if L == R {
   
        return twoSelectOne(P == 1, 0, -1)
    }
    if P == 1 {
   
        next := process2(L, R, K, arr, K, presum, dp)
        if next == -1 {
   
            dp[L][R][P] = -1
            return -1
        } else {
   
            dp[L][R][P] = next + presum[R+1] - presum[L]
            return next + presum[R+1] - presum[L]
        }
    } else {
   
        ans := math.MaxInt64
        // i...mid是第1块，剩下的是part-1块
        for mid := L; mid < R; mid += K - 1 {
   
            next1 := process2(L, mid, 1, arr, K, presum, dp)
            next2 := process2(mid+1, R, P-1, arr, K, presum, dp)
            if next1 == -1 || next2 == -1 {
   
                dp[L][R][P] = -1
                return -1
            } else {
   
                ans = getMin(ans, next1+next2)
            }
        }
        dp[L][R][P] = ans
        return ans
    }
}

执行结果如下：

左神java代码

2022-05-03：Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第

2022-05-03：Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。 假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

输入：stones = [2,1]。 输出：true。 解释：游戏进行如下：

• 回合 1：Alice 可以移除任意一个石子。
• 回合 2：Bob 移除剩下的石子。 已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

力扣2029. 石子游戏 IX。

答案2022-05-03：

这道题很难想到，直接记住结论。 偶0只有1：b赢。偶0只有2：b赢。 偶0有1有2：a赢。 奇0：1和2差的绝对值大于2，a赢；否则b赢。

代码用rust编写。代码如下：

fn main() {
    let mut arr: Vec<isize> = vec![1, 2, 3, 3, 3, 10, 10, 10, 100, 100, 100];
    let ans = stone_game_ix(&mut arr);
    println!("ans = {}", ans);
}

fn stone_game_ix(stones: &mut Vec<isize>) -> bool {
    let mut counts: Vec<isize> = vec![0, 0, 0];
    for i in 0..stones.len() {
        counts[(stones[i as usize] % 3) as usize] += 1;
    }
    if counts[0] % 2 == 0 {
        counts[1] != 0 && counts[2] != 0
    } else {
        counts[1] - counts[2] > 2 || counts[2] - counts[1] > 2
    }
}

执行结果如下：

左神java代码

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

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

答案2023-04-20：

算法流程：

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

动态规划过程：

1. 定义状态：设 dp[i][j] 表示前 i 个石头在限制条件下可以得到的最大重量；
2. 初始化状态：dp[0][j] = 0，表示前 0 个石头在限制条件下无法得到任何重量；dp[i][0] = 0，表示在不限制目标重量的情况下无法得到任何重量；
3. 状态转移方程：对于第 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])
   

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

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

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

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

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

关于[Swift Weekly Contest 126]LeetCode1000. 合并石头的最低成本 | Minimum Cost to Merge Stones的介绍已经告一段落，感谢您的耐心阅读，如果想了解更多关于2021-08-24：合并石头的最低成本。有 N 堆石头排成一排，第 i 堆中有 stones [i] 块石头。每次移动（move、2021-08-24：合并石头的最低成本。有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的、2022-05-03：Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第、2023-04-20：有一堆石头，用整数数组 stones 表示 其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎 假设石头的重量分别为 x 和的相关信息，请在本站寻找。