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

最后一块石头的重量 II

题面

leetcode题目

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

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

• 如果 \(x = y\)，那么两块石头都会被完全粉碎；
• 如果 \(x\neq y\)，那么重量为 \(x\) 的石头将会完全粉碎，而重量为 \(y\) 的石头新重量为 \(y-x\)。
• 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 \(0\)。

example

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

数据范围

• \(1 \leq stones.length \leq 30\)
• \(1 \leq stones[i] \leq 100\)

题解

总体思路

考虑存在结果\(ret\)表示为最后剩余石头的最小可能重量，因为我们一定能找到一个序列，进行相互的碰撞直到获得最后一个石头(或者不剩石头)，所以\(ret\)一定是存在的。令: \[ ret = \sum_{i=0}^{n-1} k_i\times stones_i , k_i \in \{-1,1\} \tag{1}\] 于是我们考虑按\(k_i\)的值为\(1\)还是\(-1\)把石头分为两堆，令其中重量小的一堆的总重量为\(sum_a\)，石头的总重量为\(sum\)，则另一堆的总重量的为\(sum_b=sum-sum_a\)。那么 \[ret = sum_b - sum_a = (sum - sum_a) - sum_a = sum - 2\times sum_a \tag{2}\]

对于\((2)\)式，其合法的情况显然为\(sum - 2\times sum_a > 0\)，即\(sum_a < \frac{sum}{2} \tag{3}\)。要使\(ret\)最小，则要使\(sum_a\)最大，于是问题转化为在满足\((3)\)式下的01背包问题。
考虑\(dp[i][j]\)表示在选择完\(i\)石头后是否能凑出重量\(j\)，那么:

• 当\(j < stones[i]\)时，显然不能选择石头\(i\)，此时\(dp[i][j] = dp[i-1][j]\)
• 当\(j\geq stones[i]\) 时，存在选择或者不选择石头\(i\)的选项，那么\(dp[i][j]\)在\(dp[i-1][j]\)或者\(dp[i-1][j-stones[i]]\)中有一个可能凑出时可以凑出。

于是有： \[ dp[i][j] = \left\{ \begin{array}{rcl} dp[i-1][j] & & {j < stones[i]}\\ dp[i-1][j]\vee dp[i-1][j-stones[i]] & & {j \geq stones[i]} \end{array} \right. \]

代码

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
#define _DEBUG
using namespace std;
class Solution
{
public:
    const int MAX = 110;
    int lastStoneWeightII(vector<int> &stones)
    {
        int len = stones.size();
        int sum = 0;
        for (int i = 0; i < len; i++)
        {
            sum += stones[i];
        }

        bool dp[len + 1][MAX];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = true;
        for (int i = 1; i <= len; i++)
        {
            int stone = stones[i - 1];
            for (int j = 0; j <= sum / 2; j++)
            {
                if (j < stone)
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    if (dp[i - 1][j] || dp[i - 1][j - stone])
                    {
                        dp[i][j] = true;
                    }
                }
            }
        }
        for (int i = sum / 2; i >= 0; i--)
        {
            if (dp[len][i])
            {
                return sum - 2 * i;
            }
        }
        return 0;
    }
};

// for test
int main()
{
    Solution s;
    vector<int> t1{2, 7, 4, 1, 8, 1};
    cout << s.lastStoneWeightII(t1) << endl;
    vector<int> t2{31, 26, 33, 21, 40};
    cout << s.lastStoneWeightII(t2) << endl;

    return 0;
}