1049. 最后一块石头的重量 II - 已题解语言：Python, C#, C++, Java, JavaScript, Go, Ruby

力扣题解最佳实践 > 动态规划 > 1049. 最后一块石头的重量 II > 已用 Python, C#, C++, Java, JavaScript, Go, Ruby 语言实现 > 贡献代码或转发

力扣链接：1049. 最后一块石头的重量 II，难度：中等。

有一堆石头，用整数数组 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

提示 1

Think of the final answer as a sum of weights with + or - sign symbols in front of each weight. Actually, all sums with 1 of each sign symbol are possible.

提示 2

Use dynamic programming: for every possible sum with N stones, those sums +x or -x is possible with N+1 stones, where x is the value of the newest stone. (This overcounts sums that are all positive or all negative, but those don't matter.)

题解 1: 从右到左遍历 dp
题解 2: 从左到右遍历 dp（推荐）

思路
上一题 下一题

这道题可以用蛮力法解决，就是找出数组所有的子集，看每个子集数组的和是否接近完整数组和的一半，找最接近的那个。但是当我们看到stones.length <= 30的时候，我们就知道这样的解法一定会超时。
所以我们需要换个思路，你之前的题目相当于求拆分后两个数组和的最小差值，如果找到一个子集数组，它的和最接近完整数组和的一半，那么它就是我们想要的子集数组。
那么这道题就变成了0/1背包问题，它属于动态规划，动态规划是指当前题的答案可以从前面的同类题中推导出来，因此用dp数组来记录所有的答案。
0/1背包问题的核心逻辑是使用二维dp数组或者一维dp滚动数组，先遍历物品，再遍历背包大小（逆序或者使用dp.clone），然后引用当前'物品'大小对应的前一个值。
使用二维dp数组需要记住的东西很多，面试的时候很难一次性写对，这里就不描述了。

“动态规划”的模式

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，“按顺序”填入dp网格数据。
根据dp网格数据，推导出“递推公式”。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个对等数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，“按顺序”填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出“递推公式”。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个对等数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

“0/1背包问题”的模式

因为“0/1背包问题”属于“动态规划”，所以我会用“动态规划”的模式讲解。

确定数组dp的每个值代表的含义。
- 首选一维滚动数组，代码简洁。
- 确定什么是“物品”，什么是“背包”。
- 如果dp[j]是一个布尔值，则dp[j]表示是否可以前i个物品的和得到j。
- 如果dp[j]是一个数值，则dp[j]表示是利用前i个物品，dp[j]能达到的所求问题的极限值。
初始化数组dp的值。
- 确定“背包”的大小。需要让背包大小再加1，即插入dp[0]做为起始点，方便理解和引用。
- dp[0]有时需要特殊处理。
根据一个示例，“按顺序”填入dp网格数据。
- 先在外层循环中，遍历物品。
- 后在内层循环中，遍历背包大小。
  - 在遍历背包大小时，由于dp[j]取决于dp[j]和dp[j - weights[i]]，因此我们应该从右到左遍历dp数组。
  - 请思考是否可以从从左到右遍历dp数组？
根据dp网格数据，推导出“递推公式”。
- 如果dp[j]是一个布尔值：
```
dp[j] = dp[j] || dp[j - weights[i]]
```
- 如果dp[j]是一个数值：
```
dp[j] = min_or_max(dp[j], dp[j - weights[i]] + values[i])
```
写出程序，并打印dp数组，不合预期就调整。

步骤

确定dp[j]的含义
- dp[j]表示是否可以用前i个stones的和得到j。
- dp[j]是一个布尔值。
确定 dp 数组的初始值
- 举个例子：
```
stones = [2,7,4,1,8,1]，所以 '总和的一半' 是 11。
背包的 `size` 就是 '11 + 1'，‘物品’ 是 'stones'。
所以初始化后，'dp' 数组将是：
#   0 1 2 3 4 5 6 7 8 9 10 11
#   T F F F F F F F F F F  F  # dp
# 2
# 7
# 4
# 1
# 8
# 1
```
- dp[0] 设为 true，表示不使用任何 stones 也可以得到一个空背包。另外，它作为起始值，后面的 dp[j] 将依赖于它。如果它是 false，则 dp[j] 的所有值都将为 false。
- dp[j] = false (j != 0)，表示不使用 stones 就不可能得到 j。

根据一个示例，“按顺序”填入dp网格数据。

1. 使用第一块石头 '2'。
#   0 1 2 3 4 5 6 7 8 9 10 11
#   T F F F F F F F F F F  F
# 2 T F T F F F F F F F F  F  # dp

2. 使用第二颗石头“7”。
#   0 1 2 3 4 5 6 7 8 9 10 11
#   T F F F F F F F F F F  F
# 2 T F T F F F F F F F F  F
# 7 T F T F F F F T F T F  F

3. 使用第三颗石头“4”。
#   0 1 2 3 4 5 6 7 8 9 10 11
#   T F F F F F F F F F F  F
# 2 T F T F F F F F F F F  F
# 7 T F T F F F F F T F F  F
# 4 T F T F T F T T F T F  T # dp
# ...

根据dp网格数据，推导出“递推公式”。
```
dp[j] = dp[j] || dp[j - stones[i]]
```
写出程序，并打印dp数组，不合预期就调整。

复杂度

时间复杂度

O(n * sum/2)

空间复杂度

O(sum/2)

Python #

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sum_ = sum(stones)

        dp = [False] * (sum_ // 2 + 1)
        dp[0] = True

        for stone in stones:
            # If not traversing in reverse order, the newly assigned value `dp[j]` will act as `dp[j - stone]` later,
            # then the subsequent `dp[j]` will be affected. But each `stone` can only be used once!
            for j in range(len(dp) - 1, 0, -1):
                if j < stone:
                    break
                dp[j] = dp[j] or dp[j - stone]

        for i in range(len(dp) - 1, -1, -1):
            if dp[i]:
                return sum_ - i * 2

C# #

public class Solution {
    public int LastStoneWeightII(int[] stones) {
        var sum = stones.Sum();

        var dp = new bool[sum / 2 + 1];
        dp[0] = true;

        foreach (int stone in stones) {
            for (var j = dp.GetUpperBound(0); j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }

        for (var j = dp.GetUpperBound(0); j >= 0; j--) {
            if (dp[j]) {
                return sum - j * 2;
            }
        }

        throw new ArithmeticException("lastStoneWeightII() has a logical error!");
    }
}

C++ #

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        auto sum = reduce(stones.begin(), stones.end());

        auto dp = vector<bool>(sum / 2 + 1);
        dp[0] = true;

        for (auto stone : stones) {
            for (auto j = dp.size() - 1; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }

        for (auto i = dp.size() - 1; i >= 0; i--) {
            if (dp[i]) {
                return sum - i * 2;
            }
        }

        throw logic_error("lastStoneWeightII() has a logical error!");
    }
};

Java #

class Solution {
    public int lastStoneWeightII(int[] stones) {
        var sum = IntStream.of(stones).sum();

        var dp = new boolean[sum / 2 + 1];
        dp[0] = true;

        for (var stone : stones) {
            for (var j = dp.length - 1; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }

        for (var j = dp.length - 1; j >= 0; j--) {
            if (dp[j]) {
                return sum - j * 2;
            }
        }

        throw new ArithmeticException("lastStoneWeightII() has a logical error!");
    }
}

JavaScript #

var lastStoneWeightII = function (stones) {
  const sum = _.sum(stones)

  const dp = Array(Math.floor(sum / 2) + 1).fill(false)
  dp[0] = true

  for (const stone of stones) {
    for (let j = dp.length - 1; j >= stone; j--) {
      dp[j] = dp[j] || dp[j - stone]
    }
  }

  for (let j = dp.length - 1; j >= 0; j--) {
    if (dp[j]) {
      return sum - j * 2
    }
  }
};

Go #

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, stone := range stones {
        sum += stone
    }

    dp := make([]bool, sum / 2 + 1)
    dp[0] = true

    for _, stone := range stones {
        for j := len(dp) - 1; j >= stone; j-- {
            dp[j] = dp[j] || dp[j - stone]
        }
    }

    for j := len(dp) - 1; j >= 0; j-- {
        if dp[j] {
            return sum - j * 2
        }
    }

    return -1 // This line should be unreachable. It represents function has a logical error.
}

Ruby #

def last_stone_weight_ii(stones)
  sum = stones.sum

  dp = Array.new(sum / 2 + 1, false)
  dp[0] = true

  stones.each do |stone|
    (1...dp.size).reverse_each do |j|
      break if j < stone

      dp[j] = dp[j] || dp[j - stone]
    end
  end

  (0...dp.size).reverse_each do |j|
    return sum - j * 2 if dp[j]
  end
end

其它语言

欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 1049. 最后一块石头的重量 II。

题解2的思路：从左到右遍历 dp（推荐）

在方案 1中，遍历顺序是 从右到左，这真的很重要。

面试的时候，你需要记住它。有什么办法可以不用担心遍历顺序？

点击查看答案

只要把原dp复制一份，并引用复制品的值，就不用担心原dp值被修改了。

复杂度

时间复杂度

O(n * sum/2)

空间复杂度

O(n * sum/2)

Python #

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sum_ = sum(stones)

        dp = [False] * (sum_ // 2 + 1)
        dp[0] = True

        for stone in stones:
            dc = dp.copy()

            for j in range(stone, len(dp)):
                dp[j] = dc[j] or dc[j - stone]

        for i in range(len(dp) - 1, -1, -1):
            if dp[i]:
                return sum_ - i * 2

C# #

public class Solution
{
    public int LastStoneWeightII(int[] stones)
    {
        int sum = stones.Sum();

        var dp = new bool[sum / 2 + 1];
        dp[0] = true;

        foreach (int stone in stones)
        {
            var dc = (bool[]) dp.Clone();

            for (var j = stone; j < dp.Length; j++)
            {
                dp[j] = dc[j] || dc[j - stone];
            }
        }

        for (var j = dp.GetUpperBound(0); j >= 0; j--)
        {
            if (dp[j])
            {
                return sum - j * 2;
            }
        }

        throw new ArithmeticException("lastStoneWeightII() has a logical error!");
    }
}

C++ #

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        auto sum = reduce(stones.begin(), stones.end());

        auto dp = vector<bool>(sum / 2 + 1);
        dp[0] = true;

        for (auto stone : stones) {
            auto dc = dp;

            for (auto j = stone; j < dp.size(); j++) {
                dp[j] = dc[j] || dc[j - stone];
            }
        }

        for (auto i = dp.size() - 1; i >= 0; i--) {
            if (dp[i]) {
                return sum - i * 2;
            }
        }

        throw logic_error("lastStoneWeightII() has a logical error!");
    }
};

Java #

class Solution {
    public int lastStoneWeightII(int[] stones) {
        var sum = IntStream.of(stones).sum();

        var dp = new boolean[sum / 2 + 1];
        dp[0] = true;

        for (var stone : stones) {
            var dc = dp.clone();

            for (var j = stone; j < dp.length; j++) {
                dp[j] = dc[j] || dc[j - stone];
            }
        }

        for (var j = dp.length - 1; j >= 0; j--) {
            if (dp[j]) {
                return sum - j * 2;
            }
        }

        throw new ArithmeticException("lastStoneWeightII() has a logical error!");
    }
}

JavaScript #

var lastStoneWeightII = function (stones) {
  const sum = _.sum(stones)

  const dp = Array(Math.floor(sum / 2) + 1).fill(false)
  dp[0] = true

  for (const stone of stones) {
    const dc = [...dp]

    for (let j = stone; j < dp.length; j++) {
      dp[j] = dc[j] || dc[j - stone]
    }
  }

  for (let j = dp.length - 1; j >= 0; j--) {
    if (dp[j]) {
      return sum - j * 2
    }
  }
};

Go #

func lastStoneWeightII(stones []int) int {
    sum := 0
    for _, stone := range stones {
        sum += stone
    }

    dp := make([]bool, sum / 2 + 1)
    dp[0] = true

    for _, stone := range stones {
        dc := slices.Clone(dp)

        for j := stone; j < len(dp); j++ {
            dp[j] = dc[j] || dc[j - stone]
        }
    }

    for j := len(dp) - 1; j >= 0; j-- {
        if dp[j] {
            return sum - j * 2
        }
    }

    return -1 // This line should be unreachable. It represents function has a logical error.
}

Ruby #

def last_stone_weight_ii(stones)
  sum = stones.sum

  dp = Array.new(sum / 2 + 1, false)
  dp[0] = true

  stones.each do |stone|
    dc = dp.clone

    (stone...dp.size).each do |j|
      dp[j] = dc[j] || dc[j - stone]
    end
  end

  (0...dp.size).reverse_each do |j|
    return sum - j * 2 if dp[j]
  end
end

其它语言

欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 1049. 最后一块石头的重量 II。

上一题下一题

游客

全部题解

Welcome !

力扣题解最佳实践 > 动态规划 > 1049. 最后一块石头的重量 II > 已用 Python, C#, C++, Java, JavaScript, Go, Ruby 语言实现 > 贡献代码 或 转发

示例 1:

示例 2:

约束:

思路 上一题下一题

“动态规划”的模式

“动态规划”分为五步

细说这五步

“0/1背包问题”的模式

步骤

复杂度

时间复杂度

空间复杂度

Python #

C# #

C++ #

Java #

JavaScript #

Go #

Ruby #

其它语言

题解2的思路：从左到右遍历 dp（推荐）

复杂度

时间复杂度

空间复杂度

Python #

C# #

C++ #

Java #

JavaScript #

Go #

Ruby #

其它语言

力扣题解最佳实践 > 动态规划 > 1049. 最后一块石头的重量 II > 已用 Python, C#, C++, Java, JavaScript, Go, Ruby 语言实现 > 贡献代码或转发

思路
上一题下一题