Reference: LeetCode

Difficulty: Easy

Twitter OA 2019 | Coloring the blocks

My Post: [Java] Dynamic Programming is Cool (Explanation)

## Problem

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.

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.

**Note:** All costs are positive integers.

**Example:**

1 | Input: [[17,2,17],[16,16,5],[14,3,19]] |

## Analysis

### DP

**Define:**`dp[i][j]`

is the minimum cost of painting`i`

-th house with color`j`

.**Recurrence:**(3 states)`dp[i][0]`

= min(`dp[i-1][1]`

,`dp[i-1][2]`

) +`costs[i][0]`

`dp[i][1]`

= min(`dp[i-1][0]`

,`dp[i-1][2]`

) +`costs[i][1]`

`dp[i][2]`

= min(`dp[i-1][0]`

,`dp[i-1][1]`

) +`costs[i][2]`

**Init:**`dp[0][0]`

=`cost[i][0]`

`dp[0][1]`

=`cost[i][1]`

`dp[0][2]`

=`cost[i][2]`

1 | public int minCost(int[][] costs) { |

**Time:** $O(N)$**Space:** $O(N)$

Comment