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代码
