# Paint House

## Problem#

There is a row of `n` houses where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an `n x 3` cost matrix `costs`.

• For example, `costs` is the cost of painting house `0` with the color red; `costs` is the cost of painting house 1 with color green, and so on.

Return the minimum cost to paint all houses.

For example,

```Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.
```
```Input: costs = [[7,6,2]]
Output: 2
```

Constraints:

• `costs.length == n`
• `costs[i].length == 3`
• `1 <= n <= 100`
• `1 <= costs[i][j] <= 20`

## Solution#

### Brute Force#

``````public int MinCost(int[][] costs)
{
return Math.Min(PaintCost(0, 0), Math.Min(PaintCost(0, 1), PaintCost(0, 2)));

int PaintCost(int i, int color)
{
int totalCost = costs[i][color];

if (i == costs.Length - 1)
{

}
else if (color == 0)    // Red
{
totalCost += Math.Min(PaintCost(i + 1, 1), PaintCost(i + 1, 2));
}
else if (color == 1)    // Blue
{
totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 2));
}
else if (color == 2)    // Green
{
totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 1));
}

}
}
``````

#### Complexity Analysis#

Suppose `N` is the length of `costs`.

• Time Complexity: At each step we generate two subtree and the height of the tree is `N`. The total number of generated nodes is 2N. Since, we traverse all the nodes, then the complexity will be O(2N).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

### Top-down Dynamic Programming#

``````public int MinCost(int[][] costs)
{
Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();
return Math.Min(PaintCost(0, 0), Math.Min(PaintCost(0, 1), PaintCost(0, 2)));

int PaintCost(int i, int color)
{
if (memo.TryGetValue((i, color), out int value))
{
return value;
}

int totalCost = costs[i][color];

if (i == costs.Length - 1)
{

}
else if (color == 0)    // Red
{
totalCost += Math.Min(PaintCost(i + 1, 1), PaintCost(i + 1, 2));
}
else if (color == 1)    // Blue
{
totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 2));
}
else if (color == 2)    // Green
{
totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 1));
}

}
}
``````

#### Complexity Analysis#

Suppose `N` is the length of `costs`.

• Time Complexity: Since we cache each `PaintCost(i,color)`, then we will perform at most N recursive calls, thus the complexity is O(N).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

### Bottom-up Dynamic Programming#

``````public int MinCost(int[][] costs)
{
for (int n = costs.Length - 2; n >= 0; n--)
{
// Total cost of painting the nth house red.
costs[n] += Math.Min(costs[n + 1], costs[n + 1]);

// Total cost of painting the nth house blue.
costs[n] += Math.Min(costs[n + 1], costs[n + 1]);

// Total cost of painting the nth house green.
costs[n] += Math.Min(costs[n + 1], costs[n + 1]);
}

return Math.Min(costs, Math.Min(costs, costs));
}
``````

#### Complexity Analysis#

Suppose `N` is the length of `costs`.

• Time Complexity: Since we iterate linearly up to `N`, then the complexity is O(N).
• Space Complexity: O(1) since we only need to reuse the input `costs` array.