There is a row of $n$ houses, where each house can be painted in one of $3$ 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 house i with a certain color is represented by an $n imes 3$ cost matrix costs. For example, costs[0][0] is the cost of painting house $0$ with the color red, costs[1][2] is the cost of painting house $1$ with the color green, and so on.

Return the minimum cost to paint all houses.

Constraints:

• costs.length $= n$

• costs[i].length $= 3$

• $1 \leq n \leq 100$

• $1 \leq$ costs[i][j] $\leq 20$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.