2022-02-01：粉刷房子 II。 假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种

2022-02-01：粉刷房子 II。 假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n*k 的矩阵来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。 注意： 所有花费均为正整数。 示例： 输入: [[1,5,3],[2,9,4]] 输出: 5 解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. 进阶： 您能否在 O(nk) 的时间复杂度下解决此问题？ 力扣265。

答案2022-02-01：

方法一：dp[i][j]。动态规划。 方法二：求第i号房子的最优加颜色和次优加颜色，依次推导下去。 时间复杂度：O(N)。 空间复杂度：O(1)。

代码用golang编写。代码如下：

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
}

执行结果如下：

左神java代码