1049. Last Stone Weight II

same as leetcode 416, but this one caculate the difference.

time: O(n*m)

space: O(n*m)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int num : stones) { // add them all
            sum += num;
        }
        
        int n = stones.length;
        int m = sum/2; // become 01 backpack problems, target is sum/2
        
        boolean dp[][] = new boolean[n+1][m+1];
        
        int min = Integer.MAX_VALUE;
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= stones[i-1]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - stones[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
                
                if (dp[i][j]) { // if can fit to sum/2 pack, caculate the diff, the current weight size is j
                    int diff = Math.abs(sum - j*2);
                    min = Math.min(min, diff);
                }
            }
        }
        return min; 
}

second solution

https://leetcode.com/problems/last-stone-weight-ii/discuss/294888/JavaC%2B%2BPython-Easy-Knapsacks-DP

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int num : stones) { // add them all
            sum += num;
        }
        
        int n = stones.length;
        int m = sum/2; // become 01 backpack problems, target is sum/2
        
        int dp[][] = new int[n+1][m+1];
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= stones[i-1]) {
                    dp[i][j] = Math.max(
                        dp[i-1][j], 
                        dp[i-1][j - stones[i-1]] + stones[i-1]
                    );
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return sum - 2*dp[n][m]; // at last, dp[n][m] fit to sum/2's result, so *2
    }
}