题目分析

题目描述非常有趣，小伙伴们深入挖掘其中的隐藏信息，先尝试求解一下吧。

动态规划

题目的隐藏信息是，将石头分为最接近的两堆。然后两堆的差值就是题目的最优解。下面就转化为如何将石头分为最接近的两堆。

石头分为两堆，必然有一堆不多于另一堆，假设共有x个石头，那么将一定有一堆不多于x / 2，有一堆不少于x / 2。因此我们用一个大小为x / 2的包裹去装石头，看能够装入的最大重量就是较小堆的最大值，此时两堆石头最接近，是本题的最优解，下面转化为0-1背包问题，用dp[i][j]表示前i个石头装入容量为j的背包，能放入的石头的最大重量。
$$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]])$$
因为第i层状态仅与第i - 1层有关，可以使用一维dp进行求解。

算法的**时间复杂度为$O(n \cdot sum)$，空间复杂度为$O(sum)$**，其中sum为所有石头重量之和

下面是C++语言的题解

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sums = accumulate(stones.begin(), stones.end(), 0);
        int stone = sums >> 1;
        vector<int> dp(stone + 1);
        for (int x : stones) {
            for (int i = stone; i >= x; i--) {
                dp[i] = max(dp[i], dp[i - x] + x);
            }
        }
        return sums - 2 * dp.back();
    }
};

下面是Kotlin语言的题解

class Solution {
    fun lastStoneWeightII(stones: IntArray): Int {
        var sums = 0
        for (x in stones) { sums += x }
        val stone = sums.shr(1)
        val dp = IntArray(stone + 1)
        for (x in stones) {
            for (i in stone downTo x) {
                dp[i] = Math.max(dp[i], dp[i - x] + x)
            }
        }
        return sums - 2 * dp.last()
    }
}

刷题总结

0-1背包问题是程序员必知必会的算法之一，很多题目都是从0-1背包问题转化而来，小伙伴们一定要打好基础，多多总结，多做练习。