題目網址：https://leetcode.cn/problems/last-stone-weight-ii/

題意：有一堆石頭, 用整數 array stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合, 從中選出任意兩塊石頭, 然後將它們一起粉碎。假設石頭的重量分別為 x 和 y, 且 x ≤ y。粉碎的可能結果如下：

  • 若 x == y, 則兩塊石頭都會被完全粉碎
  • 若 x != y, 則重量為 x 的石頭將會完全粉碎, 而重量為 y 的石頭新重量為 y - x

最後, 最多只會剩下一塊石頭。返回此石頭最小的可能重量, 如果沒有石頭剩下, 則返回 0。

Solution 1：

想法：假設 stones = [a, b, c, d], 每次取出兩顆來粉碎, 可以想成每次取出兩數, 然後在這兩數前面分別加上 +/- 號, e.g. 其中一種可能的解為 a - b + c - d（類似 494. Target Sum）。因此, 利用 hash set s 保存前 i - 1 個石頭所產生的和, 然後一一取出這些和, 並加上第 i 個數分別取 +/- 號之值

e.g. stones = [1, 2]

  • 初始值：s = {0}
  • 第一輪：s = {0 + 1, 0 - 1} = {1, - 1}
  • 第二輪：s = {1 + 2, 1 - 2, -1 + 2, -1 - 2} = {-3, -1, 1, -3}

➔ ≥ 0 的最小值為 1 = +2 - 1

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        unordered_set<int> s({0}); // 初始為 0

        for (const auto& cur : stones) {
            unordered_set<int> prevSet = s;
            s.clear();

            for (const auto& prevSum : prevSet) {
                s.emplace(prevSum + cur);
                s.emplace(prevSum - cur);
            }
        }

        // 取出 ≥ 0 的最小和
        int res = INT_MAX;
        for (const auto& sum : s) {
            if (sum >= 0 && sum < res) {
                res = sum;
            }
        }

        return res;
    }
};
  • time：$O(\sum\limits_{i = 1}^n{(i \cdot 2^{i})})$ ➔ for loop, 當到第 i 顆石頭時, s 中最多有 $2^i$ 個數（每個石頭有兩種選擇）, 其中 n 為 stones 的長度
  • space：$O(2^n)$ ➔ s

Solution 2：

想法：利用 DP

1. 定義狀態：

  • dp[i][j]：stones[1:i] 是否能湊出 j

2. 得到轉移方程：

  • dp[i][j] = dp[i - 1][j - stones[i]] || dp[i - 1][j + stones[i]]

3. 初始化：

  • 首先, 會在 stones 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[0][0] = 1：代表沒有元素時, 什麼都不取可以湊出 0

4. 注意事項：

  • 本題 dp[i][j] 的 j 之範圍為 [-sum, sum], 但 index 不允許負數, 因此統一加上 offset = sum, 將其 mapping 到範圍 [0, 2 * abs(sum)]
  • 最後取的答案是 ≥ 0 的正整數, 因此是從 0 開始算, 而非 sum
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        const int n = stones.size();
        const int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<vector<bool>> dp(n + 1, vector<bool>(2 * abs(sum) + 1, false));

        stones.emplace(stones.begin(), 0);

        const int offset = sum; // sum 必為正整數
        dp[0][0 + offset] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = -sum; j <= sum; ++j) {
                // 避免越界
                if (j - stones[i] >= -sum && j - stones[i] <= sum) {
                    dp[i][j + offset] = dp[i][j + offset] || dp[i - 1][j - stones[i] + offset];
                }

                if (j + stones[i] >= -sum && j + stones[i] <= sum) {
                    dp[i][j + offset] = dp[i][j + offset] || dp[i - 1][j + stones[i] + offset];
                }
            }
        }

        // 只考慮 ≥ 0 之和
        for (int i = 0; i <= sum; ++i) {
            if (dp[n][i + offset]) {
                return i;
            }
        }

        return 0;
    }
};
  • time：$O(sum \cdot n)$ ➔ for loop
  • space：$O(sum \cdot n)$ ➔ dp

Solution 3：

想法：利用 DP, Solution 2 的改進, 實際上 dp[i][j + offset] 只會用到上一列 dp[i - 1][X], 故不需要開到 $O(sum \cdot n)$ 的空間, 只需 $O(sum)$ 的空間即可

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        const int n = stones.size();
        const int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<bool> dp(2 * abs(sum) + 1, false);

        stones.emplace(stones.begin(), 0);

        const int offset = sum; // sum 必為正整數
        dp[0 + offset] = true;

        for (int i = 1; i <= n; ++i) {
            vector<bool> nextRow(2 * sum + 1, false);

            for (int j = -sum; j <= sum; ++j) {
                if (j - stones[i] >= -sum && j - stones[i] <= sum) {
                    nextRow[j + offset] = nextRow[j + offset] || dp[j - stones[i] + offset];
                }

                if (j + stones[i] >= -sum && j + stones[i] <= sum) {
                    nextRow[j + offset] = nextRow[j + offset] || dp[j + stones[i] + offset];
                }
            }

            dp = move(nextRow);
        }

        for (int i = 0; i <= sum; ++i) {
            if (dp[i + offset]) {
                return i;
            }
        }

        return 0;
    }
};
  • time：$O(sum \cdot n)$ ➔ for loop
  • space：$O(sum)$ ➔ dp