动态规划，可以自定义颜色数，求解《剑指 Offer II 091. 粉刷房子》
例题
剑指 Offer II 091. 粉刷房子
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。
答案
动态规划
var minCost = function(costs) { // 自定义颜色数
const n = costs.length, m = 3
let dp = new Uint16Array(m)
for (let i = 0; i < n; i++) {
const ndp = new Uint16Array(m)
for (let j = 0; j < m; j++) {
let minInt = Number.MAX_SAFE_INTEGER
for (let k = 1; k < m; k++) {
const t = (j + k) % m
if (minInt > dp[t]) minInt = dp[t]
}
ndp[j] = minInt + costs[i][j]
}
dp = ndp
}
return Math.min.apply(null, dp)
};var minCost = function(costs) { // 空间压缩
const n = costs.length
let a = b = c = 0
for (let i = 0; i < n; i++) {
const ta = a, tb = b
a = Math.min(b, c) + costs[i][0]
b = Math.min(ta, c) + costs[i][1]
c = Math.min(ta, tb) + costs[i][2]
}
return Math.min(a, b, c)
};function minCost(costs: number[][]): number {
const n = costs.length, m = 3
let dp = new Uint16Array(m)
for (let i = 0; i < n; i++) {
const ndp = new Uint16Array(m)
for (let j = 0; j < m; j++) {
let minInt = Number.MAX_SAFE_INTEGER
for (let k = 1; k < m; k++) {
const t = (j + k) % m
if (minInt > dp[t]) minInt = dp[t]
}
ndp[j] = minInt + costs[i][j]
}
dp = ndp
}
return Math.min.apply(null, Array.from(dp))
};func minCost(costs [][]int) int {
m := 3
dp := make([]int, m)
for _, cost := range costs {
ndp := make([]int, m)
for j := 0; j < m; j++ {
minInt := int(^uint(0) >> 1)
for k := 1; k < m; k++ {
t := (j + k) % m
if minInt > dp[t] {
minInt = dp[t]
}
}
ndp[j] = minInt + cost[j]
}
dp = ndp
}
return min(dp)
}
func min(nums []int) int {
minInt := int(^uint(0) >> 1)
for _, num := range nums {
if minInt > num {
minInt = num
}
}
return minInt
}class Solution {
function minCost($costs) {
$n = count($costs);
$m = 3;
$dp = array_fill(0, $m, 0);
for ($i = 0; $i < $n; $i++) {
$ndp = array_fill(0, $m, 0);
for ($j = 0; $j < $m; $j++) {
$minInt = PHP_INT_MAX;
for ($k = 1; $k < $m; $k++) {
$t = ($j + $k) % $m;
if ($minInt > $dp[$t]) $minInt = $dp[$t];
}
$ndp[$j] = $minInt + $costs[$i][$j];
}
$dp = $ndp;
}
return min($dp);
}
}class Solution {
public int minCost(int[][] costs) {
int n = costs.length, m = 3;
int[] dp = new int[m];
for (int[] cost : costs) {
int[] ndp = new int[m];
for (int j = 0; j < m; j++) {
int minInt = Integer.MAX_VALUE;
for (int k = 1; k < m; k++) {
int t = (j + k) % m;
if (minInt > dp[t]) minInt = dp[t];
}
ndp[j] = minInt + cost[j];
}
dp = ndp;
}
return Arrays.stream(dp).min().getAsInt();
}
}class Solution(object): # Python 2.7.12
def minCost(self, costs):
m = 3
dp = [0] * m
for cost in costs:
ndp = [0] * m
for j in range(0, m):
minInt = sys.maxint
for k in range(1, m):
t = (j + k) % m
if minInt > dp[t]: minInt = dp[t]
ndp[j] = minInt + cost[j]
dp = ndp
return min(dp)class Solution: # Python 3.10
def minCost(self, costs: List[List[int]]) -> int:
m = 3
dp = [0] * m
for cost in costs:
ndp = [0] * m
for j in range(0, m):
minInt = sys.maxsize
for k in range(1, m):
t = (j + k) % m
if minInt > dp[t]: minInt = dp[t]
ndp[j] = minInt + cost[j]
dp = ndp
return min(dp)MIN(a, b) a < b ? a : b
int minCost(int** costs, int costsSize, int* costsColSize){
int m = 3;
int dp[m];
for (int i = 0; i < m; i++) dp[i] = 0;
for (int i = 0; i < costsSize; i++) {
int ndp[m];
for (int j = 0; j < m; j++) {
int minInt = INT_MAX;
for (int k = 1; k < m; k++) {
int t = (j + k) % m;
if (minInt > dp[t]) minInt = dp[t];
}
ndp[j] = minInt + costs[i][j];
}
memcpy(dp, ndp, m * 4);
}
int r = INT_MAX;
for (int i = 0; i < m; i++) r = MIN(r, dp[i]);
return r;
}class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int m = 3;
int dp[m];
for (vector<int> cost : costs) {
int ndp[m];
for (int j = 0; j < m; j++) {
int minInt = INT_MAX;
for (int k = 1; k < m; k++) {
int t = (j + k) % m;
if (minInt > dp[t]) minInt = dp[t];
}
ndp[j] = minInt + cost[j];
}
memcpy(dp, ndp, m * 4);
}
return *min_element(dp, dp + m);
}
};public class Solution {
public int MinCost(int[][] costs) {
int[] dp = new int[3];
int m = 3;
foreach (int[] cost in costs) {
int[] ndp = new int[3];
for (int j = 0; j < m; j++) {
int minInt = int.MaxValue;
for (int k = 1; k < m; k++) {
int t = (j + k) % m;
if (minInt > dp[t]) minInt = dp[t];
}
ndp[j] = minInt + cost[j];
}
dp = ndp;
}
return dp.Min();
}
}