Paint House

medium dp

Problem

There are n houses in a row. Painting each house red, blue, or green has its own cost. No two adjacent houses share a color. Return the minimum total cost.

Inputcosts = [[17,2,17],[16,16,5],[14,3,19]]

Output10

2 + 5 + 3 = 10 (blue → green → blue).

costs (rows by ';', cols by ',')

def min_cost(costs):
    r = b = g = 0
    for cr, cb, cg in costs:
        r, b, g = cr + min(b, g), cb + min(r, g), cg + min(r, b)
    return min(r, b, g)

function minCost(costs) {
  let r = 0, b = 0, g = 0;
  for (const [cr, cb, cg] of costs) {
    [r, b, g] = [cr + Math.min(b, g), cb + Math.min(r, g), cg + Math.min(r, b)];
  }
  return Math.min(r, b, g);
}

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

int minCost(vector>& costs) {
    int r = 0, b = 0, g = 0;
    for (auto& c : costs) {
        int nr = c[0] + min(b, g);
        int nb = c[1] + min(r, g);
        int ng = c[2] + min(r, b);
        r = nr; b = nb; g = ng;
    }
    return min({r, b, g});
}

Explanation

The key insight is that to paint a house a certain color, you only care about the cheapest way to have finished the previous house in one of the two other colors. You never need to look further back than one house.

So we keep three running totals: r, b, g — the minimum total cost to paint everything up to the current house, ending in red, blue, or green. We start them all at 0.

For each house with costs cr, cb, cg, the new red total is its own red price plus the cheaper of the old blue and green totals: cr + min(b, g). We do the same for blue and green, updating all three at once so the old values are reused correctly.

Example: [[17,2,17],[16,16,5],[14,3,19]]. After house 0 the totals are (17, 2, 17). After house 1, blue stays expensive but green becomes 5 + min(17, 2) = 7. After house 2 the cheapest is 3 + min(...), and min(r, b, g) ends up 10.

Because we sweep each house once and only keep three numbers, the whole thing runs in linear time with constant memory.

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