# LeetCode 256: Paint House

## Problem Restatement

We are given `n` houses in a row.

Each house can be painted one of three colors:

| Color Index | Color |
|---|---|
| `0` | Red |
| `1` | Blue |
| `2` | Green |

The painting cost is given by an `n x 3` matrix called `costs`.

For example:

```python
costs[i][0]
```

is the cost to paint house `i` red.

We need to paint every house such that no two adjacent houses have the same color.

Return the minimum total cost.

The constraints are `costs.length == n`, `costs[i].length == 3`, `1 <= n <= 100`, and `1 <= costs[i][j] <= 20`. The standard examples include `[[17,2,17],[16,16,5],[14,3,19]] -> 10` and `[[7,6,2]] -> 2`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A matrix `costs` with `n` rows and `3` columns |
| Output | Minimum total painting cost |
| Rule | Adjacent houses cannot have the same color |
| Colors | Red, blue, green |

Example function shape:

```python
def minCost(costs: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
costs = [
    [17, 2, 17],
    [16, 16, 5],
    [14, 3, 19],
]
```

One optimal painting is:

| House | Color | Cost |
|---|---|---|
| `0` | Blue | `2` |
| `1` | Green | `5` |
| `2` | Blue | `3` |

Total cost:

```python
2 + 5 + 3 = 10
```

Answer:

```python
10
```

Example 2:

```python
costs = [[7, 6, 2]]
```

There is only one house.

Choose the cheapest color.

Answer:

```python
2
```

## First Thought: Try Every Coloring

A direct solution is to try every possible color for every house.

For each house, there are three choices.

So for `n` houses, the number of possible colorings is:

```python
3 ** n
```

Then we keep only the colorings where adjacent houses use different colors and take the cheapest one.

This gives the right answer, but it is far too slow.

## Problem With Brute Force

The brute force search repeats the same decisions many times.

For example, after painting the first few houses, the only information that matters for the next house is:

1. The previous house's color.
2. The minimum cost so far.

We do not need to remember the full color sequence.

That is the dynamic programming structure.

## Key Insight

For each house, track three values:

| State | Meaning |
|---|---|
| `red` | Minimum cost so far if current house is red |
| `blue` | Minimum cost so far if current house is blue |
| `green` | Minimum cost so far if current house is green |

When painting the current house red, the previous house cannot be red.

So the best cost ending in red is:

```python
min(previous_blue, previous_green) + current_red_cost
```

Similarly:

```python
new_blue = min(previous_red, previous_green) + current_blue_cost
new_green = min(previous_red, previous_blue) + current_green_cost
```

This is enough because future houses only care about the color of the immediately previous house.

## Algorithm

Start with:

```python
red = blue = green = 0
```

These variables represent the minimum cost before painting any house.

For each row:

```python
cost_red, cost_blue, cost_green
```

compute the new totals:

```python
new_red = min(blue, green) + cost_red
new_blue = min(red, green) + cost_blue
new_green = min(red, blue) + cost_green
```

Then update:

```python
red = new_red
blue = new_blue
green = new_green
```

After all houses are processed, return:

```python
min(red, blue, green)
```

## Walkthrough

Use:

```python
costs = [
    [17, 2, 17],
    [16, 16, 5],
    [14, 3, 19],
]
```

Before any house:

```python
red = 0
blue = 0
green = 0
```

After house `0`:

```python
red = 17
blue = 2
green = 17
```

After house `1`:

```python
red = min(2, 17) + 16 = 18
blue = min(17, 17) + 16 = 33
green = min(17, 2) + 5 = 7
```

So:

```python
red = 18
blue = 33
green = 7
```

After house `2`:

```python
red = min(33, 7) + 14 = 21
blue = min(18, 7) + 3 = 10
green = min(18, 33) + 19 = 37
```

Final answer:

```python
min(21, 10, 37) = 10
```

## Correctness

For each house `i`, maintain this invariant:

`red`, `blue`, and `green` store the minimum cost to paint houses `0` through `i` when house `i` is painted red, blue, or green respectively.

The invariant is true after the first house because the cost is simply the cost of painting that house with each color.

Assume it is true for the previous house.

For the current house, if we paint it red, the previous house must be blue or green. The cheapest valid previous total is therefore:

```python
min(previous_blue, previous_green)
```

Adding the current red cost gives the cheapest valid total ending in red.

The same reasoning applies to blue and green.

Thus the invariant remains true after every house.

At the end, the last house may have any color, so the minimum valid total is:

```python
min(red, blue, green)
```

Therefore the algorithm returns the minimum total painting cost.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We process each house once |
| Space | `O(1)` | We store only three running values |

## Implementation

```python
class Solution:
    def minCost(self, costs: list[list[int]]) -> int:
        red = blue = green = 0

        for cost_red, cost_blue, cost_green in costs:
            red, blue, green = (
                min(blue, green) + cost_red,
                min(red, green) + cost_blue,
                min(red, blue) + cost_green,
            )

        return min(red, blue, green)
```

## Code Explanation

We initialize all three states to zero:

```python
red = blue = green = 0
```

This means no cost has been paid before painting the first house.

For each house:

```python
for cost_red, cost_blue, cost_green in costs:
```

we compute the minimum cost ending with each color.

The assignment:

```python
red, blue, green = (
    min(blue, green) + cost_red,
    min(red, green) + cost_blue,
    min(red, blue) + cost_green,
)
```

uses the old values of `red`, `blue`, and `green` on the right side before updating them.

This is important. It prevents the new `red` value from accidentally affecting the computation of `blue` or `green`.

Finally:

```python
return min(red, blue, green)
```

returns the cheapest valid total after painting all houses.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minCost([[17, 2, 17], [16, 16, 5], [14, 3, 19]]) == 10
    assert s.minCost([[7, 6, 2]]) == 2
    assert s.minCost([[1, 5, 3], [2, 9, 4]]) == 5
    assert s.minCost([[5, 8, 6], [19, 14, 13], [7, 5, 12]]) == 24
    assert s.minCost([[20, 18, 4], [9, 9, 10], [6, 2, 8], [6, 2, 19]]) == 22

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official multi-house example | Confirms standard DP behavior |
| Single house | Chooses cheapest color |
| Two houses | Checks adjacent color rule |
| Three houses | Confirms transitions across rows |
| Larger case | Checks repeated updates |