256. Paint the house

The title

Suppose you have a row of n houses, each of which can be painted in one of three colors: red, blue, or green, and you need to paint all the houses so that the two adjacent houses are not the same color.

Of course, because the price of different colors of paint is different in the market, the cost of painting a house in different colors is also different. The cost of painting each house a different color is expressed as an N x 3 positive integer matrix costs.

For example, costs[0][0] represents the cost of painting House no. 0 red. Costs [1][2] represents the cost of painting House No. 1 green, and so on.

Please calculate the minimum cost of painting all the houses.

Example 1

Input: costs = [[17,2,17],[16,16,5],[14,3,19]] output: 10 description: house 0 is painted blue, house 1 is painted green, and house 2 is painted blue. Minimum cost: 2 + 5 + 3 = 10.Copy the code

Example 2

Costs = [[7,6,2]Copy the code

prompt

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

Answer key

Dynamic programming

What color of the current house is affected by the color of the previous house and needs to find the optimal solution according to the Costscostscosts array decision

Recursive analysis:

  • Houses can only be painted red, blue and green
  • If the current house can be painted red, the previous house must be blue or green
  • Same for other colors
  • If the house can be painted red, take a house to paint blue or green minimum
  • Use an array to record the minimum cost of painting room III red, blue, and green

The recursive formula is:

[red] = min(f[i-1][blue], F [i-1][green])+costs[I][red]

Edit the code as follows:

var minCost = function (costs) {
  const len = costs.length
  const dp = []
  for (let i = 0; i <= len; i++) dp[i] = []
  dp[0] = costs[0]
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.min(dp[i - 1] [1], dp[i - 1] [2]) + costs[i][0]
    dp[i][1] = Math.min(dp[i - 1] [0], dp[i - 1] [2]) + costs[i][1]
    dp[i][2] = Math.min(dp[i - 1] [0], dp[i - 1] [1]) + costs[i][2]}return Math.min(... dp[len -1])}Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section