涂色问题 DP：粉刷房子与K种颜色

粉刷房子（LeetCode 256）

n 栋房子，相邻颜色不同，3 种颜色，求最低花费：

public int minCost(int[][] costs) {
    int r = costs[0][0], g = costs[0][1], b = costs[0][2];
    for (int i = 1; i < costs.length; i++) {
        int nr = costs[i][0] + Math.min(g, b);
        int ng = costs[i][1] + Math.min(r, b);
        int nb = costs[i][2] + Math.min(r, g);
        r = nr; g = ng; b = nb;
    }
    return Math.min(r, Math.min(g, b));
}

粉刷房子 II（LeetCode 265）

k 种颜色，相邻颜色不同，维护最小值和次小值（避免 O(nk²)）：

public int minCostII(int[][] costs) {
    int n = costs.length, k = costs[0].length;
    // min1: 最小值, min2: 次小值（不含 idx1 列的最小），idx1: 最小值的列索引
    int min1 = 0, min2 = 0, idx1 = -1;
    for (int i = 0; i < n; i++) {
        int newMin1 = Integer.MAX_VALUE, newMin2 = Integer.MAX_VALUE, newIdx1 = -1;
        for (int j = 0; j < k; j++) {
            int cost = costs[i][j] + (j == idx1 ? min2 : min1);
            if (cost < newMin1) { newMin2 = newMin1; newMin1 = cost; newIdx1 = j; }
            else if (cost < newMin2) newMin2 = cost;
        }
        min1 = newMin1; min2 = newMin2; idx1 = newIdx1;
    }
    return min1;
}

奇怪的打印机（LeetCode 664）

打印机每次打印一段连续相同字符（可覆盖原来的字符），求最少打印次数：

区间DP：dp[i][j] = 打印 s[i..j] 的最少次数：

public int strangePrinter(String s) {
    int n = s.length();
    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++) {
            dp[i][j] = dp[i][j-1] + 1; // 先打 s[i..j-1]，再单独打 s[j]
            for (int k = i; k < j; k++) {
                if (s.charAt(k) == s.charAt(j)) { // s[k] 和 s[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];
}

最大矩形（LeetCode 85）

在0/1矩阵中，找含1的最大矩形面积——按行压缩为柱状图，再求柱状图最大面积：

public int maximalRectangle(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[] heights = new int[n];
    int ans = 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;
        }
        ans = Math.max(ans, largestRectangleInHistogram(heights));
    }
    return ans;
}

private int largestRectangleInHistogram(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int ans = 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 top = stack.pop();
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            ans = Math.max(ans, heights[top] * width);
        }
        stack.push(i);
    }
    return ans;
}

总结