February 1, 2022: painting house II. If there is a row of houses, N in total, each

2022-02-01： Paint the house II.

If there is a row of houses , common n individual , Every house can be painted k One of the colors , You need to paint all the houses and make the two adjacent houses not the same color .

Of course , Because the prices of different colors of paint on the market are different , So the cost of painting the house in different colors is different . The cost of painting each house in a different color is one n*k The matrix of .

for example ,costs0 It means the first one 0 House No. 1 painted 0 The cost of color No ;costs1 It means the first one 1 House No. 1 painted 2 The cost of color No , And so on . Please work out the minimum cost of painting all the houses .

Be careful ：

All costs are positive integers .

Example ：

Input : [1,5,3,2,9,4]

Output : 5

explain : take 0 House No. 1 painted 0 Number color ,1 House No. 1 painted 2 Number color . Minimum cost : 1 + 4 = 5;

  Or will  0  House No. 1 painted  2  Number color ,1  House No. 1 painted  0  Number color . Minimum cost : 3 + 2 = 5.

Advanced ：

Can you wait at O(nk) To solve this problem under the time complexity of ？

Power button 265.

answer 2022-02-01：

Method 1 ：dpi. Dynamic programming .

Method 2 ： Please i The best plus color and the second best plus color , It is deduced in turn .

Time complexity ：O(N).

Spatial complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "math"
)

func main() {
    costs := [][]int{{1, 5, 3}, {2, 9, 4}}
    ret := minCostII(costs)
    fmt.Println(ret)
}

// costs[i][k] i For House No k Cost of color brush 
//  Must let 0...N-1 Our houses are adjacent to each other in different colors 
//  Returns the minimum cost 
func minCostII(costs [][]int) int {
    N := len(costs)
    if N == 0 {
        return 0
    }
    K := len(costs[0])
    //  The lowest price ever achieved 、 The color to get the minimum cost 
    preMin1 := 0
    preEnd1 := -1
    //  The second small price obtained before 、 Get the color of the next small price 
    preMin2 := 0
    preEnd2 := -1
    for i := 0; i < N; i++ { // i house 
        curMin1 := math.MaxInt64
        curEnd1 := -1
        curMin2 := math.MaxInt64
        curEnd2 := -1
        for j := 0; j < K; j++ { // j Color ！
            if j != preEnd1 {
                if preMin1+costs[i][j] < curMin1 {
                    curMin2 = curMin1
                    curEnd2 = curEnd1
                    curMin1 = preMin1 + costs[i][j]
                    curEnd1 = j
                } else if preMin1+costs[i][j] < curMin2 {
                    curMin2 = preMin1 + costs[i][j]
                    curEnd2 = j
                }
            } else if j != preEnd2 {
                if preMin2+costs[i][j] < curMin1 {
                    curMin2 = curMin1
                    curEnd2 = curEnd1
                    curMin1 = preMin2 + costs[i][j]
                    curEnd1 = j
                } else if preMin2+costs[i][j] < curMin2 {
                    curMin2 = preMin2 + costs[i][j]
                    curEnd2 = j
                }
            }
        }
        preMin1 = curMin1
        preEnd1 = curEnd1
        preMin2 = curMin2
        preEnd2 = curEnd2
    }
    return preMin1
}

The results are as follows ：

picture

Zuo Shen java Code