题目描述
这里有$n$个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。
费用通过一个$n \times 3$ 的矩阵给出，比如$cost[0][0]$表示房屋$0$染红色的费用，$cost[1][2]$表示房屋$1$染绿色的费用。
样例1
输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.
样例2
输入: [[1,2,3],[1,4,6]]
输出: 3
算法
(DP) $O(n)$
dp[i][j]表示第i幢房子涂j的颜色最小的花费总和，即从前一幢房子的状态dp[i-1][k] (k != j)中选一个不同颜色且最小的再加上给第i幢房子涂j颜色的costs。
-
初始化状态
dp[0][i]=costs[0][i] -
从左往右遍历每一幢房子，计算到该幢房子涂每种颜色的最小花费，状态转移方程是
dp[i][j] = min{dp[i-1][k] +costs[i][j]} (k != j) -
答案为到最后一幢房子涂每种颜色花费中的最小值，即
min(dp[n-1][k]),k=0,1,2
Java 代码
public class Solution {
/**
* @param costs: n x 3 cost matrix
* @return: An integer, the minimum cost to paint all houses
*/
public int minCost(int[][] costs) {
int n = costs.length;
if (n == 0) {
return 0;
}
//dp[i][j]表示第i幢房子涂j的颜色最小的总和
//初始化状态dp[0][i]=costs[0][i]
int[][] dp = new int[2][3];
for (int i= 0; i < 3; i++) {
dp[0][i] = costs[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
dp[i&1][j] = Integer.MAX_VALUE;
for (int k = 0; k < 3; k++) {
if (k != j) {
dp[i&1][j] = Math.min(dp[i&1][j], dp[i&1^1][k] + costs[i][j]);
}
}
}
}
return Math.min(dp[n&1^1][0], Math.min(dp[n&1^1][1], dp[n&1^1][2]) );
}
}
