14.17 Paint House

14.17.1 Problem Metadata

14.17.2 Description

You are given an n x 3 matrix costs where costs[i][j] denotes the cost of painting house i with color j. Adjacent houses must not share a color. Return the minimum total cost to paint all houses.

14.17.3 Examples

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10

14.17.4 Constraints

  • 1 <= n <= 100
  • 0 <= costs[i][j] <= 10^4

14.17.5 Solution - Rolling DP

14.17.5.1 Walkthrough

Keep three running totals for the cost of painting up to the current house when the current house ends in red, green, or blue. For house i, the red cost equals costs[i][0] + min(previousGreen, previousBlue), and similarly for the other colors. Update the running totals and take the minimum at the end.

14.17.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

14.17.5.3 Implementation Steps

  1. Initialize red = green = blue = 0.
  2. For each house:
    1. Compute new totals for each color by adding its cost to the minimum of the other two previous totals.
    2. Update red, green, blue to these new totals.
  3. Return min(red, green, blue).

14.17.5.4 Code - Java

public int minCost(int[][] costs) {
    int red = 0, green = 0, blue = 0;

    for (int[] cost : costs) {
        int newRed = cost[0] + Math.min(green, blue);
        int newGreen = cost[1] + Math.min(red, blue);
        int newBlue = cost[2] + Math.min(red, green);
        red = newRed;
        green = newGreen;
        blue = newBlue;
    }

    return Math.min(red, Math.min(green, blue));
}