1049. Last Stone Weight II

 一刷 06/2022

Version #1 0/1 Knapsack with 2D DP

没看懂证明

关于为什么0/1 Knapsack可以化简成 1D DP

因为如果dp[i - 1][j]为true，那么dp[i][j] 一定为true

而dp[i - 1][j - num]为true，可以导出dp[i][j]也为true

相当于一个accumulate的结果

Time O(N*SUM)

Space O(N*SUM)

Runtime: 4 ms, faster than 69.37% of Java online submissions for Last Stone Weight II.

Memory Usage: 39.7 MB, less than 93.15% of Java online submissions for Last Stone Weight II.

class Solution {

    public int lastStoneWeightII(int[] stones) {

        // Divide the stones into two groups

        // [2 7 4] [1 8 1] -> pick up a pair and smash -> [1 0 3] [0 1 0] -> 3

        // The result equals to the difference of the sum of the two groups

        // dp[i][j] the previous i numbers can sum up to j

        int sum = 0;

        for (int stone : stones) {

            sum += stone;

        }

        boolean[][] dp = new boolean[stones.length + 1][sum / 2 + 1];

        dp[0][0] = true;

        for (int i = 1; i <= stones.length; i++) {

            for (int j = 0; j < dp[0].length; j++) {

                if (j == 0) {

                    dp[i][j] = true;

                    continue;

                }

                dp[i][j] = dp[i - 1][j];

                if (j >= stones[i - 1]) {

                    dp[i][j] |= dp[i - 1][j - stones[i - 1]];

                }

            }

        }

        for (int i = sum / 2; i >= 0; i--) {

            if (dp[stones.length][i]) {

                return sum - i - i;

            }

        }

        return 0;

    }

}