1049-最后一块石头的重量 II

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出 任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后， 最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

**输入：** 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]，这就是最优值。

示例 2：

**输入：** stones = [31,26,33,21,40]
**输出：** 5

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

前言：合法性证明

为了便于讨论，若最终没有石头剩下，则视作最终剩下了一块重量为 0 的石头。

用归纳法可以证明，无论按照何种顺序粉碎石头，最后一块石头的重量总是可以表示成

\sum_{i=0}^{n-1} k_i \times \textit{stones}_i,\ \ k_i\in{-1,1}

但不是所有 k_i 的取值都是合法的。例如有四块石头，其重量分别为 a，b，c，d，且满足 a\le b\le c\le d。由于石头的重量不可能增加，无论怎么操作，我们是不可能得到大小为 d+c+b-a 的石头的，该重量已经超过了 c 以及 d。

那么，上述和式的最小非负值所对应的这组 {k_i\ 是合法的吗？

我们将这组 {k_i\ 对应的石头划分成两堆，k_i=1 的石头分至一堆，k_i=-1 的石头分至另一堆。由于这是最小非负值所对应的 {k_i\，这两堆石头重量之差的绝对值也是所有划分当中最小的。

记这两堆石头重量之差的绝对值为 diff。若能找到一种粉碎方案，使得最后一块石头的重量也为 diff，那就能说明这组 {k_i\ 是合法的。

我们不断地粉碎石头。每次粉碎时，记重量最大的石头所处的堆为 A（若两堆最大重量相同则任选一堆），另一堆为 B。从 A 中取出重量最大的石头，B 中任取一石头，若没有完全粉碎，则将新石头重新放入 A。这一操作从每堆石头中减去了同样的重量，从而保证重量之差的绝对值在粉碎前后是不变的。

若出现一堆没有石头，而另一堆不止一块石头的情况，记有石头的那一堆为 A，另一堆为 B。要继续粉碎，则需要从 A 中取出一块石头移入 B，然后按规则粉碎。但移入操作让重量之差的绝对值变得更小，与事实（上文加粗文字）矛盾，所以不会出现这种情况。

因此，按照上述流程操作，最后一块石头的重量为 diff，所以这组 {k_i\ 对应着一个合法的粉碎结果。

方法一：动态规划

记石头的总重量为 sum，k_i=-1 的石头的重量之和为 neg，则其余 k_i=1 的石头的重量之和为 sum}-\textit{neg。则有

\sum_{i=0}^{n-1} k_i\cdot\textit{stones}_i = (\textit{sum}-\textit{neg})-\textit{neg} = \textit{sum}-2\cdot\textit{neg}

要使最后一块石头的重量尽可能地小，neg 需要在不超过 \lfloor \textit{sum}/2 \rfloor 的前提下尽可能地大。因此本问题可以看作是背包容量为 \lfloor \textit{sum}/2 \rfloor，物品重量和价值均为 stones}_i 的 0-1 背包问题。

对于该问题，定义二维布尔数组 dp，其中 dp}[i+1][j] 表示前 i 个石头能否凑出重量 j。特别地，dp}[0][] 为不选任何石头的状态，因此除了 dp}[0][0] 为真，其余 dp}[0][j] 全为假。

对于第 i 个石头，考虑凑出重量 j：

  • 若 j<\textit{stones}[i]，则不能选第 i 个石头，此时有 dp}[i+1][j]=\textit{dp}[i][j]；
  • 若 j\ge \textit{stones}[i]，存在选或不选两种决策，不选时有 dp}[i+1][j]=\textit{dp}[i][j]，选时需要考虑能否凑出重量 j-\textit{stones}[i]，即 dp}[i+1][j]=\textit{dp}[i][j-\textit{stones}[i]]。若二者均为假则 dp}[i+1][j] 为假，否则 dp}[i+1][j] 为真。

因此状态转移方程如下：

\textit{dp}[i+1][j]=
\begin{cases}
\textit{dp}[i][j],& j<\textit{stones}[i] \
\textit{dp}[i][j] \lor \textit{dp}[i][j-\textit{stones}[i]], & j\ge \textit{stones}[i]
\end{cases}

其中 \lor 表示逻辑或运算。求出 dp}[n][] 后，所有为真的 dp}[n][j] 中，最大的 j 即为 neg 能取到的最大值。代入 sum}-2\cdot\textit{neg 中即得到最后一块石头的最小重量。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int n = stones.size(), m = sum / 2;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[0][0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j < stones[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }
        for (int j = m;; --j) {
            if (dp[n][j]) {
                return sum - 2 * j;
            }
        }
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int weight : stones) {
            sum += weight;
        }
        int n = stones.length, m = sum / 2;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j < stones[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }
        for (int j = m;; --j) {
            if (dp[n][j]) {
                return sum - 2 * j;
            }
        }
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int sum = 0;
        foreach (int weight in stones) {
            sum += weight;
        }
        int n = stones.Length, m = sum / 2;
        bool[,] dp = new bool[n + 1, m + 1];
        dp[0, 0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j < stones[i]) {
                    dp[i + 1, j] = dp[i, j];
                } else {
                    dp[i + 1, j] = dp[i, j] || dp[i, j - stones[i]];
                }
            }
        }
        for (int j = m;; --j) {
            if (dp[n, j]) {
                return sum - 2 * j;
            }
        }
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, v := range stones {
        sum += v
    }
    n, m := len(stones), sum/2
    dp := make([][]bool, n+1)
    for i := range dp {
        dp[i] = make([]bool, m+1)
    }
    dp[0][0] = true
    for i, weight := range stones {
        for j := 0; j <= m; j++ {
            if j < weight {
                dp[i+1][j] = dp[i][j]
            } else {
                dp[i+1][j] = dp[i][j] || dp[i][j-weight]
            }
        }
    }
    for j := m; ; j-- {
        if dp[n][j] {
            return sum - 2*j
        }
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var lastStoneWeightII = function(stones) {
    let sum = 0;
    for (const weight of stones) {
        sum += weight;
    }
    const n = stones.length, m = Math.floor(sum / 2);
    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j <= m; ++j) {
            if (j < stones[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
            }
        }
    }
    for (let j = m;; --j) {
        if (dp[n][j]) {
            return sum - 2 * j;
        }
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        n, m = len(stones), total // 2
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True

        for i in range(n):
            for j in range(m + 1):
                if j < stones[i]:
                    dp[i + 1][j] = dp[i][j]
                else:
                    dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]]
        
        ans = None
        for j in range(m, -1, -1):
            if dp[n][j]:
                ans = total - 2 * j
                break
        
        return ans
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lastStoneWeightII(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; i++) {
        sum += stones[i];
    }
    int n = stonesSize, m = sum / 2;
    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < stones[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
            }
        }
    }
    for (int j = m;; --j) {
        if (dp[n][j]) {
            return sum - 2 * j;
        }
    }
}

由于 dp}[i+1][] 的每个元素值的计算只和 dp}[i][] 的元素值有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度。

对于转移方程

\textit{dp}[i+1][j]=\textit{dp}[i][j] \lor \textit{dp}[i][j-\textit{stones}[i]]

在去掉第一个维度后，若仍采用正序遍历，在计算 dp}[j] 时，dp}[j-\textit{stones}[i]] 的值已经被覆盖，这意味着 dp}[j-\textit{stones}[i]] 实际对应的是 dp}[i+1][j-\textit{stones}[i]]，即我们计算的是一个错误的转移方程

\textit{dp}[i+1][j]=\textit{dp}[i][j] \lor \textit{dp}[i+1][j-\textit{stones}[i]]

若采用倒序遍历，则可消除该错误，这种方式保证计算 dp}[j] 时，dp}[j-\textit{stones}[i]] 的值实际对应的是 dp}[i][j-\textit{stones}[i]]，从而保证转移方程与去掉维度前一致。

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int m = sum / 2;
        vector<int> dp(m + 1);
        dp[0] = true;
        for (int weight : stones) {
            for (int j = m; j >= weight; --j) {
                dp[j] = dp[j] || dp[j - weight];
            }
        }
        for (int j = m;; --j) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int weight : stones) {
            sum += weight;
        }
        int m = sum / 2;
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for (int weight : stones) {
            for (int j = m; j >= weight; --j) {
                dp[j] = dp[j] || dp[j - weight];
            }
        }
        for (int j = m;; --j) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int sum = 0;
        foreach (int weight in stones) {
            sum += weight;
        }
        int m = sum / 2;
        bool[] dp = new bool[m + 1];
        dp[0] = true;
        foreach (int weight in stones) {
            for (int j = m; j >= weight; --j) {
                dp[j] = dp[j] || dp[j - weight];
            }
        }
        for (int j = m;; --j) {
            if (dp[j]) {
                return sum - 2 * j;
            }
        }
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, v := range stones {
        sum += v
    }
    m := sum / 2
    dp := make([]bool, m+1)
    dp[0] = true
    for _, weight := range stones {
        for j := m; j >= weight; j-- {
            dp[j] = dp[j] || dp[j-weight]
        }
    }
    for j := m; ; j-- {
        if dp[j] {
            return sum - 2*j
        }
    }
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var lastStoneWeightII = function(stones) {
    let sum = 0;
    for (const weight of stones) {
        sum += weight;
    }
    const m = Math.floor(sum / 2);
    const dp = new Array(m + 1).fill(false);
    dp[0] = true;
    for (const weight of stones) {
        for (let j = m; j >= weight; --j) {
            dp[j] = dp[j] || dp[j - weight];
        }
    }
    for (let j = m;; --j) {
        if (dp[j]) {
            return sum - 2 * j;
        }
    }
};
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        n, m = len(stones), total // 2
        dp = [False] * (m + 1)
        dp[0] = True

        for weight in stones:
            for j in range(m, weight - 1, -1):
                dp[j] |= dp[j - weight]
        
        ans = None
        for j in range(m, -1, -1):
            if dp[j]:
                ans = total - 2 * j
                break
        
        return ans
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lastStoneWeightII(int* stones, int stonesSize) {
    int sum = 0;
    for (int i = 0; i < stonesSize; i++) {
        sum += stones[i];
    }
    int m = sum / 2;
    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = true;
    for (int i = 0; i < stonesSize; ++i) {
        for (int j = m; j >= stones[i]; --j) {
            dp[j] = dp[j] || dp[j - stones[i]];
        }
    }
    for (int j = m;; --j) {
        if (dp[j]) {
            return sum - 2 * j;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n\cdot \textit{sum})。其中 n 是数组 stones 的长度，sum 为 stones 所有元素之和。

  • 空间复杂度：O(\textit{sum})。

 Comments
On this page
1049-最后一块石头的重量 II