• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[LeetCode] 1049. 最后一块石头的重量 II

开发技术 开发技术 2天前 5次浏览

看来最近力扣的每日一题换成了背包啊。

这个问题并不是一个直接的背包问题,需要做一下问题转化的。

把石头尽可能的平均分成两堆,即两堆石头的总重量尽可能的相等。如果所有石头总重量和为sum的话,那么分成的两堆石头,每堆石头的重量尽可能的接近sum/2。

让这两堆石头相撞,最后剩下的最小石头,就是两堆石头重量和的差。

能想到这,接下来就是一个朴素的01背包问题了:背包总体积为sum/2,然后石头的重量就是价值,尽可能的装满背包。最后求出来的最大背包价值,就是重量和小的那一堆石头。

也就是 sum – 2 * f[n][sum/2];

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;

        int sum = 0;
        for (int i=0;i<n;i++) {
            sum += stones[i];
        }

        int v = sum / 2;

        int[][] f = new int[n+1][v+1];
        for (int i=1;i<=n;i++) {
            for (int j=0;j<=v;j++) {
                f[i][j] = f[i-1][j];
                if (i<=n&&j-stones[i-1]>=0) {
                    f[i][j] = Math.max(f[i-1][j], f[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }

        return sum - 2*f[n][v];
    }
}

程序员灯塔
转载请注明原文链接:[LeetCode] 1049. 最后一块石头的重量 II
喜欢 (0)