LeetCode 1049. Last Stone Weight II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 1049. Last Stone Weight II 原题链接中等

作者：

wzc1995 , 2019-05-20 23:18:37 , 所有人可见 , 阅读 4226

8

1

题目描述

有一堆石头，每块石头的重量都是正整数。

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

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

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

样例

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

注意

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

算法

(动态规划) $O(n \times sum)$

合并的过程就是给每个重量前赋值正号或者负号的过程，相当于把这些石头分为两组，使得两组的差值尽可能小，所以这是经典的集合划分 NP 完全问题，可以采用动态规划的方法求解。
设状态 $f(i)$ 表示是否存在一个划分，使得某组的重量总和为 $i$ 。
初始时 $f(0) = true$ ，其余为 $false$ 。
转移时，模仿 01 背包的算法，对于每个物品，有放和不放两种决策，故 $f(j) = f(j) \text{ or } f(j - stones[j])$ 。
最终答案需要枚举， $j$ 从 $\frac{sum}{2}$ 开始到 0，如果 $f(j) == true$ ，则返回 $sum - j - j$ 。

时间复杂度

状态数为 $O(n \times sum)$ ，转移时间为常数，故时间复杂度为 $O(n \times sum)$ 。

空间复杂度

需要额外 $O(sum)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size(), sum = 0;
        for (int i = 0; i < n; i++)
            sum += stones[i];

        vector<bool> f(sum + 1, false);
        f[0] = true;

        for (int i = 0; i < n; i++)
            for (int j = sum / 2; j >= stones[i]; j--)
                f[j] = f[j] || f[j - stones[i]];

        for (int i = sum / 2; i >= 0; i--)
            if (f[i])
                return sum - i - i;

        return sum;
    }
};

4 评论

simonhan 2021-06-08 10:58

impl Solution {
    pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
        let n = stones.len();
        let s = stones.iter().sum();
        let wei = (s / 2) as usize;  
        let mut dp = vec![false;wei as usize + 1];
        dp[0] = true;//最开始的时候可以分割出0的组
        for i in 0..n{
            for j in (stones[i] as usize..=wei).rev(){
                dp[j] = dp[j] || dp[j - stones[i] as usize];
            }
        }
        for i in (0..=wei).rev(){
            if dp[i]{
                return s - 2 * i as i32;
            }
        }
        s
    }
}