Saved from https://leetcode.com/problems/last-stone-weight-ii/

lc1049

class Solution {
    // A variant of the knapsack problem
    // dp[i][j]: is there a subset of stones (0 to i-1) can sum up to weight j
    // dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
    // result: last stone weight = the shortest distance between any two nodes among dp[n][0] ... dp[n][W] 
    //
    // Time: O(n * totalWeight)
    // Space: O(n * totalWeight)
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = Arrays.stream(stones).sum();
        boolean[][] dp = new boolean[stones.length + 1][totalWeight/2 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= stones.length; i++) {
            int currStone = stones[i-1];
            for (int j = 0; j < dp[0].length; j++) {
                if (dp[i-1][j] || (j >= currStone && dp[i-1][j-currStone])) {
                    dp[i][j] = true;
                }
            }
        }
        for (int i = dp[0].length - 1; i >= 0; i--) {
            if (dp[stones.length][i]) {
                return totalWeight - i - i;
            }
        }
        return 0;
    }
}