956. Tallest Billboard

Version #2 Optimized Space

88.94 %
class Solution {
    public int tallestBillboard(int[] rods) { // Space O(sum) version
        // dp[i][k] -> tallest common height for previous i rods with diff k
        // 1. don't choose rod[i] -> dp[i][k] = dp[i - 1][k]
        // 2. put rod[i] into the taller set -> dp[i][k + rod[i - 1]] = dp[i - 1][k] <- diff increased but common height not changed
        // 3. put rod[i] into the shorter set -> dp[i][Math.abs(rod[i - 1] - k)] = dp[i - 1][k] + Math.min(rod[i - 1], k)
        // 3.1 rod[i] > k -> dp[i][rod[i - 1] - k] = dp[i - 1][k] + k
        // 3.2 rod[i] < k -> dp[i][k - rod[i - 1]] = dp[i - 1][k] + rod[i - 1]
        int sum = 0, len = rods.length;
        for (int rod : rods) sum += rod;
        int[] prev = new int[sum + 1];
        Arrays.fill(prev, -1);
        prev[0] = 0;
        for (int i = 1; i <= len; i++) {
            int[] curr = new int[sum + 1];
            Arrays.fill(curr, -1);
            for (int k = 0; k + rods[i - 1] <= sum; k++) { // iterate throgh dp[i - 1]
                if (prev[k] == -1) continue; // this diff doesn't exist
                curr[k] = Math.max(curr[k], prev[k]);
                curr[k + rods[i - 1]] = Math.max(curr[k + rods[i - 1]], prev[k]);
                curr[Math.abs(rods[i - 1] - k)] = Math.max(curr[Math.abs(rods[i - 1] - k)], prev[k] + Math.min(rods[i - 1], k));
            }
            prev = curr;
        }
        return prev[0];
    }
}

Version #1 0/1 KnapSack
[2ND TRY]
95.44 %
class Solution {
    public int tallestBillboard(int[] rods) {
        // dp[i][k] -> tallest common height for previous i rods with diff k
        // 1. don't choose rod[i] -> dp[i][k] = dp[i - 1][k]
        // 2. put rod[i] into the taller set -> dp[i][k + rod[i - 1]] = dp[i - 1][k] <- diff increased but common height not changed
        // 3. put rod[i] into the shorter set -> dp[i][Math.abs(rod[i - 1] - k)] = dp[i - 1][k] + Math.min(rod[i - 1], k)
        // 3.1 rod[i] > k -> dp[i][rod[i - 1] - k] = dp[i - 1][k] + k
        // 3.2 rod[i] < k -> dp[i][k - rod[i - 1]] = dp[i - 1][k] + rod[i - 1]
        int sum = 0, len = rods.length;
        for (int rod : rods) sum += rod;
        int[][] dp = new int[len + 1][sum + 1];
        for (int i = 0; i <= len; i++) Arrays.fill(dp[i], -1);
        dp[0][0] = 0;
        for (int i = 1; i <= len; i++) {
            for (int k = 0; k + rods[i - 1] <= sum; k++) { // iterate throgh dp[i - 1]
                if (dp[i - 1][k] == -1) continue; // this diff doesn't exist
                dp[i][k] = Math.max(dp[i][k], dp[i - 1][k]);
                dp[i][k + rods[i - 1]] = Math.max(dp[i][k + rods[i - 1]], dp[i - 1][k]);
                dp[i][Math.abs(rods[i - 1] - k)] = Math.max(dp[i][Math.abs(rods[i - 1] - k)], dp[i - 1][k] + Math.min(rods[i - 1], k));
            }
        }
        return dp[len][0];
    }
}


[1ST TRY]
完全几乎不懂
空间还可以继续优化

92.86 %
class Solution {
    public int tallestBillboard(int[] rods) {
        int sum = 0;
        for (int rod : rods) sum += rod;
        int[][] dp = new int[rods.length + 1][sum + 1];
        for (int i = 0; i < rods.length + 1; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[0][0] = 0;
        // for [0,i) rods, the highest common height to reach diff
        for (int i = 1; i <= rods.length; i++) {
            int rod = rods[i - 1];
            // iterate diff of dp[i-1]
            for (int diff = 0; diff + rod <= sum; diff++) {
                if (dp[i - 1][diff] < 0) continue;
                // not add rod
                dp[i][diff] = Math.max(dp[i][diff], dp[i - 1][diff]);
                // add to the lower side
                dp[i][Math.abs(diff - rod)] = Math.max(
                    dp[i][Math.abs(diff - rod)],
                    dp[i - 1][diff] + Math.min(diff, rod));
                // add to the higher side
                dp[i][diff + rod] = Math.max(dp[i][diff + rod], dp[i - 1][diff]);
            }
        }
        return dp[rods.length][0];
    }
}