
### Problem Statement

###### There are a row of n houses, each house can be painted with one of the 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, and you need to cost the least. Return the minimum cost.

###### The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

![Paint House](https://images.unsplash.com/photo-1515041219749-89347f83291a?ixlib=rb-1.2.1&ixid=MnwxMjA3fDB8MHxzZWFyY2h8Mnx8bWluaW9ufGVufDB8fDB8fA%3D%3D&w=1000&q=80)

**INPUT**

- **[ [14,2,11],[11,14,5],[14,3,10] ]**

**OUTPUT**

- **10**

**EXPLANATION**

- Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.

**Steps To Solve**

- Think of solution without code

  - Lets say we have four house where cost of painting each color is as shown in distribution.

    |           | 1   | 2   | 3   | 4   |
    | --------- | --- | --- | --- | --- |
    | **Red**   | 1   | 5   | 3   | 1   |
    | **Blue**  | 5   | 8   | 2   | 2   |
    | **Green** | 7   | 4   | 9   | 4   |

  - Lets assume that it is mandatory to put a color on a house and calculate our cost.
  - Example: if we have to paint red in 1st house min cost is 1,blue in 1st house costs min 5 and green in 1st house costs 7.
    | | 1 | 2 | 3 | 4 |
    | --------- | --- | --- | --- | --- |
    | **Red** | 1 | 10 | 8 | 8 |
    | **Blue** | 5 | 8 | 7 | 10 |
    | **Green** | 7 | 5 | 18 | 11 |
  - Lets now check for 2nd house,we have to color it red mandatorily , for that we can't paint previous house red , so we choose from min cost between blue and green for the 1st house and add it to cost of painting red in 2nd house i.e **min(7,5) + 5 = 10**.
  - Similarly we calculate by painting blue to 2nd house mandatorily, cost = min(cost of red in 1st,cost of green in 1st) + cost of blue in 2nd house i.e **min(1,7) + 8 = 9**.
  - When we calculate by painting green to 2nd house mandatorily, cost = min(cost of red in 1st,cost of blue in 1st) + cost of green in 2nd house i.e **min(1,5) + 4 = 5**.
  - similarly we calculate for 3rd house , from the minimum cost calculated for 2nd house.
  - Example : If we want to paint blue to 3rd house,cost = min(cost of red in 2nd,cost of green in 2nd) + cost of blue in 3rd = **min(10,5) + 2 = 7**.
  - Finally we take min from all the cost of painting our 4th house i.e **min(8,10,11) = 8**.

```js
function minCost(costs) {
  let n = costs.length;
  if (n === 0) return 0;
  let dp = new Array(n).fill(0).map(() => new Array(3).fill(0));

  dp[0][0] = costs[0][0];
  dp[0][1] = costs[0][1];
  dp[0][2] = costs[0][2];

  for (let i = 1; i < n; i++) {
    dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
    dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
    dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
  }

  return Math.min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]);
}
```

###### Time and Space Complexity

Time Complexity is **O(N)**.
Space complexity in this case is **O(N)**.
