漆栅栏，漆墙，再漆房
Paint Fence
惭愧啊，想了半天自己也没想到好解法，觉得自己还没把这类 array DP 的问题做熟。
其实这题和 House robber 还有 Fibonacci Number 非常像， 都是 T(n) 取决于 T(n - 1) 和 T(n - 2)，在 House Robber 里，我们在取值上有一个连续性的制约：不能偷位置连续的房子；在这题里，我们刷当前位置的时候，也有颜色上的制约，我们需要的是做些思考，把这个制约找出来。
对除第一个以外的Fence，都有两个状态，diffColor代表当前状态和之前没关系，sameColor代表和上一步用了一样的颜色。当前的diffColor=(k-1)*(diffColor+sameColor). 当前的sameColor等于上一步的diffColor。
public int numWays(int n, int k) {
if(n == 0) return 0;
else if(n == 1) return k;
int diffColorCounts = k*(k-1);
int sameColorCounts = k;
for(int i=2; i<n; i++) {
int temp = diffColorCounts;
diffColorCounts = (diffColorCounts + sameColorCounts) * (k-1);
sameColorCounts = temp;
}
return diffColorCounts + sameColorCounts;
}
原始写法，两个状态，same数组和diff数组。
public int numWays(int n, int k) {
if (n == 0 || k == 0) return 0;
if (n == 1) return k;
// same[i] means the ith post has the same color with the (i-1)th post.
int[] same = new int[n];
// diff[i] means the ith post has a different color with the (i-1)th post.
int[] diff = new int[n];
same[0] = same[1] = k;
diff[0] = k;
diff[1] = k * (k - 1);
for (int i = 2; i < n; ++i) {
same[i] = diff[i-1];
diff[i] = (k - 1) * same[i-1] + (k - 1) * diff[i-1];
}
return same[n-1] + diff[n-1];
}
Paint House
这道题是"no two adjacent", 上一题是"no more than two", 一字只差, 上一段错误代码,
dp[i][j]=min(dp[i-1][t], dp[i-2][t]+cost[i-2][t])+cost[i][j]; t!=j
public int minCost(int[][] cost) {
if(cost==null || cost.length==0 || cost[0].length==0) return 0;
int m = cost.length; int n = cost[0].length;
int[][] dp = new int[m+1][n+1];
for(int i=0;i<3;i++){
dp[0][i] = 0;
dp[1][i] = cost[0][i];
}
for(int i=2;i<=m;i++)
for(int j=0;j<3;j++){
int min = Integer.MAX_VALUE;
for(int k=0;k<3;k++){
if(k==j) {continue;}
min = Math.min(min,dp[i-1][k]);
min = Math.min(min,dp[i-2][k]+cost[i-2][j]);
}
dp[i][j] = min+cost[i-1][j];
}
int ans = Integer.MAX_VALUE;
for(int j=0;j<3;j++){
ans = Math.min(ans, dp[m][j]););
}
return ans;
}
正确代码, 没有用滚动数组优化.
public int minCost(int[][] cost) {
if(cost==null || cost.length==0 || cost[0].length==0) return 0;
int m = cost.length; int n = cost[0].length;
int[][] dp = new int[m+1][n+1];
for(int i=0;i<3;i++){
dp[0][i] = 0;
dp[1][i] = cost[0][i];
}
for(int i=2;i<=m;i++)
for(int j=0;j<3;j++){
int min = Integer.MAX_VALUE;
for(int k=0;k<3;k++){
if(k==j) {continue;}
min = Math.min(min,dp[i-1][k]);
}
dp[i][j] = min+cost[i-1][j];
}
int ans = Integer.MAX_VALUE;
for(int j=0;j<3;j++){
ans = Math.min(ans, dp[m][j]);
}
return ans;
}
我们当前的涂漆选择和最小价值都取决于前一块，首先颜色不能一样，其次两种颜色的选择中，我们要选总 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]);
}
(FB) Paint House II
O(n * k * k) 的算法非常直观，顺着上一题的思路就行了。用滚动数组空间优化到了O(k), 复杂度为O(n*k*k)
public int minCostII(int[][] cost) {
if(cost==null || cost.length==0 || cost[0].length==0) return 0;
int m = cost.length; int n = cost[0].length;
int[][] dp = new int[2][n];
for(int i=0;i<n;i++){
dp[0][i] = 0;
dp[1][i] = cost[0][i];
}
for(int i=2;i<=m;i++)
for(int j=0;j<n;j++){
int min = Integer.MAX_VALUE;
for(int k=0;k<n;k++){
if(k==j) {continue;}
min = Math.min(min,dp[(i-1)%2][k]);
}
dp[i%2][j] = min+cost[i-1][j];
}
int ans = Integer.MAX_VALUE;
for(int j=0;j<n;j++){
ans = Math.min(ans, dp[m%2][j]);
}
return ans;
}
要注意这题多了一个条件：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%. (没理解T_T)
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;
}
参考论坛之后，这题还有更巧妙的 O(1) 空间做法，时间复杂度依然是 O(nk) 但是常数系数更低。
- 保存之前的 1st 小cost和其颜色；
- 保存之前的 2nd 小cost;
- 扫新位置的时候，如果发现试图染色的编号 j == 1st 小的 index, 就直接拿 2nd 小 cost; 其他照旧。
- 扫新一轮循环的时候，依次更新几个变量
- 我们只需要保存两层循环中，6个变量的值就可以了。
优化点在最内一层循环, 判断不与上一个位置颜色相等的时候, 可以通过只判断与上一位置最小val的颜色不等就可以. 计算当前值的时候如果与最小值颜色不等, 取最小值; 否则取第二小值.
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;
}
}