Painting Problems DP: House Painting and K-Colors

Paint House I (LeetCode 256)

Given $n$ houses, each can be painted in 3 colors. No two adjacent houses can have the same color. Minimize the total cost.

public int minCost(int[][] costs) {
    // Track minimum cost for each color on current house
    int r = costs[0][0], g = costs[0][1], b = costs[0][2];
    
    for (int i = 1; i < costs.length; i++) {
        // currentRed = currentCost + min(prevGreen, prevBlue)
        int nextR = costs[i][0] + Math.min(g, b);
        int nextG = costs[i][1] + Math.min(r, b);
        int nextB = costs[i][2] + Math.min(r, g);
        r = nextR; g = nextG; b = nextB;
    }
    return Math.min(r, Math.min(g, b));
}

Paint House II (LeetCode 265)

Paint $n$ houses using $k$ colors. No adjacent houses can share a color.

Optimization: To avoid $O(N \cdot K^2)$ by checking every other color for each house, track the Minimum cost and the Second Minimum cost of the previous house.

public int minCostII(int[][] costs) {
    if (costs.length == 0) return 0;
    int k = costs[0].length;
    
    // min1: global min cost, min2: second min cost, color1: color that yield min1
    int min1 = 0, min2 = 0, color1 = -1;
    
    for (int i = 0; i < costs.length; i++) {
        int nextMin1 = Integer.MAX_VALUE, nextMin2 = Integer.MAX_VALUE, nextColor1 = -1;
        for (int j = 0; j < k; j++) {
            // If current color is same as previous min1's color, use min2
            int currentCost = costs[i][j] + (j == color1 ? min2 : min1);
            
            if (currentCost < nextMin1) {
                nextMin2 = nextMin1;
                nextMin1 = currentCost;
                nextColor1 = j;
            } else if (currentCost < nextMin2) {
                nextMin2 = currentCost;
            }
        }
        min1 = nextMin1; min2 = nextMin2; color1 = nextColor1;
    }
    return min1;
}

Strange Printer (LeetCode 664)

The printer prints a continuous sequence of the same character in one turn. It can overwrite previously printed characters. Find minimum turns for string s.

Interval DP: dp[i][j] = Min turns to print range [i, j].

public int strangePrinter(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] dp = new int[n][n];
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            // Initial assumption: print s[j] in a new separate turn
            dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++) {
                // If s[k] matches s[j], they can be printed in the same turn
                if (s.charAt(k) == s.charAt(j)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0));
                }
            }
        }
    }
    return dp[0][n - 1];
}

Maximal Rectangle (LeetCode 85)

Given a 2D binary matrix, find the largest rectangle containing only 1s.

Technique: Compress each row into a histogram and solve using "Largest Rectangle in Histogram" (monotonic stack).

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[] heights = new int[n];
    int maxArea = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            heights[j] = (matrix[i][j] == '0') ? 0 : heights[j] + 1;
        }
        maxArea = Math.max(maxArea, calculateHistogramArea(heights));
    }
    return maxArea;
}

private int calculateHistogramArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Summary Summary Table