惭愧啊，想了半天自己也没想到好解法，觉得自己还没把这类 array DP 的问题做熟。
其实这题和 House robber 还有 Fibonacci Number 非常像， 都是 T(n) 取决于 T(n - 1) 和 T(n - 2)，在 House Robber 里，我们在取值上有一个连续性的制约：不能偷位置连续的房子；在这题里，我们刷当前位置的时候，也有颜色上的制约，我们需要的是做些思考，把这个制约找出来。
在刷第 n 块栅栏颜色的时候，要么要和 n - 1 的颜色不一样，要么和 n - 2 的颜色不一样。
满足 “颜色不一样” 的选择，显然是 k - 1 种，于是
T[n] = (k - 1) * (T[n - 1] + T[n - 2]);
public class Solution {
public int numWays(int n, int k) {
if(n == 0) return 0;
if(n == 1) return k;
if(n == 2) return k * k;
int[] dp = new int[3];
dp[0] = 0;
dp[1] = k;
dp[2] = k * k;
for(int i = 3; i <= n; i++){
dp[i % 3] = (k - 1) * (dp[(i - 1) % 3] + dp[(i - 2) % 3]);
}
return dp[n % 3];
}
}
吸取了上一题的教训之后，做这题时候思路就明朗多了。
我们当前的涂漆选择和最小价值都取决于前一块，首先颜色不能一样，其次两种颜色的选择中，我们要选总 cost 最小的。
一种最简单直接的思路就是，开三个数组，分别代表着以当前位置结尾，刷 "RGB" 所能得到的最小 cost，往复循环即可，因为只需要保存两个状态，所以时间复杂度也是 O(1).
要注意可能会有在当前位置上两种颜色的涂漆 cost 一样的情况，不能随意选择，因为可能下一个位置上就会出现差异。
类似 best time to buy and sell stock with cooldown，dp[] 的数量等于操作与状态的数量，代表着“由此操作结尾”。
public class Solution {
public int minCost(int[][] costs) {
if(costs == null || costs.length == 0) return 0;
int n = costs.length;
int[] minRed = new int[2];
int[] minBlue = new int[2];
int[] minGreen = new int[2];
minRed[0] = 0; minBlue[0] = 0; minGreen[0] = 0;
for(int i = 1; i <= n; i++){
minRed[i % 2] = costs[i - 1][0] + Math.min(minBlue[(i - 1) % 2], minGreen[(i - 1) % 2]);
minBlue[i % 2] = costs[i - 1][1] + Math.min(minRed[(i - 1) % 2], minGreen[(i - 1) % 2]);
minGreen[i % 2] = costs[i - 1][2] + Math.min(minBlue[(i - 1) % 2], minRed[(i - 1) % 2]);
}
return Math.min(minRed[n % 2], Math.min(minBlue[n % 2], minGreen[n % 2]));
}
}
论坛中另一种巧妙但是比较偷的解法是，直接在 cost[][] 上做更新，想法不错，可能的问题是，我们破坏了原有的 cost[][] 信息。
public class Solution {
public int minCost(int[][] costs) {
if(costs==null||costs.length==0){
return 0;
}
for(int i=1; i<costs.length; i++){
costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
}
int n = costs.length-1;
return Math.min(Math.min(costs[n][0], costs[n][1]), costs[n][2]);
}
O(n * k * k) 的算法非常直观，顺着上一题的思路就行了。
要注意这题多了一个条件：The cost of painting each house with a certain color is different，换句话说，不用再担心当前的 cost 一样，需要记录每一步不同颜色的 cost 确保算法正确性的问题了。
但是这不意味着，贪心法就是正确的，因为 localMin 不意味着 gloalMin，在当前位置选择总 cost 最低的选择，有可能会遇到下一步所有其他颜色 cost 都特别高，但是却已经不能再选同样颜色的境地。
居然一次 AC .. 虽然说代码比较粗糙。
dp[i][j] = 第 i 个房子刷 j 号漆的 min cost
dp[i][j] 的值是 当前位置刷 j 号漆的花费 cost[i][j] (忽略 off by one) 加上前一个栅栏dp[i - 1][] 里，所有不用 j 号漆的最小值。
暴力解法的话，对于每一个 j 都需要扫前一层的 j - 1 个值去找最小，来更新每个位置的 minCost Except itself，如图所示；
然而我们可以用类似 product of array except itself 的思路，去做对于每一个位置 i, left[] 和 right[] 的最小值，这样我们就可以用 O(k) 的时间和 O(k) 空间完成新一轮的 min cost except itself 数组更新。
时间复杂度 O(nk) ，空间复杂度 O(nk)，用时 6ms，超过 58.27%.
public int minCostII(int[][] costs) {
if(costs == null || costs.length == 0) return 0;
int n = costs.length;
int k = costs[0].length;
int[][] minCost = new int[n][k];
int[] minExceptSelf = new int[k];
for(int i = 0; i < n; i++){
int[] leftMin = new int[k + 1];
int[] rightMin = new int[k + 1];
leftMin[0] = Integer.MAX_VALUE;
rightMin[k] = Integer.MAX_VALUE;
for(int j = 0; j < k; j++){
minCost[i][j] = minExceptSelf[j] + costs[i][j];
}
for(int j = 1; j <= k; j++){
leftMin[j] = Math.min(leftMin[j - 1], minCost[i][j - 1]);
}
for(int j = k - 1; j >= 0; j--){
rightMin[j] = Math.min(rightMin[j + 1], minCost[i][j]);
}
for(int j = 0; j < k; j++){
minExceptSelf[j] = Math.min(leftMin[j], rightMin[j + 1]);
}
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < k; i++){
min = Math.min(min, minCost[n - 1][i]);
}
return min;
}
except self array 的构造和 index ~ 我悲剧的发现横着写多了换成竖着的有点反应不过来。。面试还是老老实实写横着的吧。
参考论坛之后，这题还有更巧妙的 O(1) 空间做法，时间复杂度依然是 O(nk) 但是常数系数更低。
扫新位置的时候，如果发现试图染色的编号 j == 1st 小的 index, 就直接拿 2nd 小 cost; 其他照旧。
可以看到，这个算法的正确性依赖于 “每个位置没有重复 cost”，我们才得以只保存两个值和一个指针就能保证正确性。
如果 cost 可以重复的话，还得靠前面那个解法。
public class Solution {
public int minCostII(int[][] costs) {
if(costs == null || costs.length == 0) return 0;
int n = costs.length;
int k = costs[0].length;
int prevMin = 0;
int prevMinPtr = -1;
int prevSecMin = 0;
for(int i = 0; i < n; i++){
int curMin = Integer.MAX_VALUE;
int curMinPtr = -1;
int curSecMin = Integer.MAX_VALUE;
for(int j = 0; j < k; j++){
int val = (j == prevMinPtr ? prevSecMin : prevMin) + costs[i][j];
if(val < curMin){
curSecMin = curMin;
curMin = val;
curMinPtr = j;
} else if (val < curSecMin){
curSecMin = val;
}
}
prevMin = curMin;
prevMinPtr = curMinPtr;
prevSecMin = curSecMin;
}
return prevMin;
}
}
