2022-02-01：粉刷房子 II。 假如有一排房子，共 n 个，每个

 或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.

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号房子用k颜色刷的花费
// 要让0...N-1的房子相邻不同色
// 返回最小花费
func minCostII(costs [][]int) int {
    N := len(costs)
    if N == 0 {
        return 0
    }
    K := len(costs[0])
    // 之前取得的最小代价、取得最小代价时的颜色
    preMin1 := 0
    preEnd1 := -1
    // 之前取得的次小代价、取得次小代价时的颜色
    preMin2 := 0
    preEnd2 := -1
    for i := 0; i < N; i++ { // i房子
        curMin1 := math.MaxInt64
        curEnd1 := -1
        curMin2 := math.MaxInt64
        curEnd2 := -1
        for j := 0; j < K; j++ { // j颜色！
            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
}