找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7733|回复: 0
收起左侧

[米群网刷题小分队] Leetcode - Paint House II

[复制链接]

62

主题

1

精华

202

积分

高级会员

Rank: 3Rank: 3

积分
202
发表于 8-20-2015 07:39 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

[分析]
使用color[j]刷house【i】时我们希望知道刷house[0,i-1]且house[i-1]刷的不是color[j]时的最小cost,于是求解过程中我们需要保留的就是dp【i】[j],表示刷完house[0, i]的最小cost且house【i】使用color[j],递推式就是dp【i】[j] = min(dp[i - 1][0]...dp[i-1][k-1]) + costs【i】[j]

思路1:直接实现上面的递推式,复杂度是O(n*k*k),非最优。
思路2:受Product of Array Except Self启发,使用两个额外数组:
minPrior【i】[j]表示使用color[0,j]刷house【i】时刷house[0,i]需要的最小cost,
minAfter【i】[j]表示使用color[0,j]刷house【i】时刷house[i,n-1]需要的最小cost.
则递推式变为dp【i】[j] = min(minPrior[i-1][j-1], minAfter[i-1][j+1]) + costs【i】[j]
复杂度是O(n*k)。因为变量较多且需要处理边界元素,很快bug free难度较高。
思路3:每次迭代house i前先计算出dp[i-1][]的最小值和次小值,
则递推式简化为dp【i】[j]=(dp[i-1][j] == preMin ? preSecondMin : preMin) + costs【i】[j]
如果dp[i-1][j]正好是刷前面所有house的最小值,由于相邻house不能同色,那这次我们就要用次小值(运气好,可能和最小值相等~) 这个思路很清晰容易实现,且空间复杂度还低,
谢谢yb君分享的巧妙方案~
  1. public class Solution {
  2.     public int minCostII(int[][] costs) {
  3.         if (costs == null || costs.length == 0)
  4.             return 0;
  5.         int n = costs.length, k = costs[0].length;
  6.         if (n > 1 && k == 1) {
  7.             return 0; // ask interviewer whether return 0 or Integer.MAX
  8.         }
  9.         //dp【i】[j]: minmum cost painting house 0-i with house i painted with color j
  10.         int[][] dp = new int[n][k];
  11.         for (int j = 0; j < k; j++)
  12.             dp[0][j] = costs[0][j];
  13.         for (int i = 1; i < n; i++) {
  14.             int preMin = Integer.MAX_VALUE;
  15.             int preSecondMin = Integer.MAX_VALUE;
  16.             for (int j = 0; j < k; j++) {
  17.                 if (dp[i - 1][j] <= preMin) {
  18.                     preSecondMin = preMin;
  19.                     preMin = dp[i - 1][j];
  20.                 } else if (dp[i - 1][j] < preSecondMin) {
  21.                     preSecondMin = dp[i - 1][j];
  22.                 }
  23.             }
  24.             
  25.             for (int j = 0; j < k; j++) {
  26.                 if (dp[i - 1][j] == preMin) {
  27.                     dp【i】[j] = preSecondMin + costs【i】[j];
  28.                 } else {
  29.                     dp【i】[j] = preMin + costs【i】[j];
  30.                 }
  31.             }
  32.         }
  33.         int min = Integer.MAX_VALUE;
  34.         for (int j = 0; j < k; j++) {
  35.             min = Math.min(min, dp[n - 1][j]);
  36.         }
  37.         return min;
  38.     }
  39.    
  40.     public int minCostII_Method1(int[][] costs) {
  41.         if (costs == null || costs.length == 0)
  42.             return 0;
  43.         int n = costs.length, k = costs[0].length;
  44.         if (n > 1 && k == 1) {
  45.             return 0;
  46.         }
  47.         if (n == 1) {
  48.             int min = costs[0][0];
  49.             for (int j = 1; j < k; j++) {
  50.                
  51.                 min = Math.min(min, costs[0][j]);
  52.             }
  53.             return min;
  54.         }
  55.         
  56.         int[][] dp = new int[n][k];
  57.         int[][] minPrior = new int[n][k];
  58.         int[][] minAfter = new int[n][k];
  59.         dp[0][0] = costs[0][0];
  60.         minPrior[0][0] = dp[0][0];
  61.         for (int j = 1; j < k; j++) {
  62.             dp[0][j] = costs[0][j];
  63.             minPrior[0][j] = Math.min(minPrior[0][j - 1], dp[0][j]);
  64.         }
  65.         minAfter[0][k - 1] = dp[0][k - 1];
  66.         for (int j = k - 2; j >= 0; j--) {
  67.             minAfter[0][j] = Math.min(minAfter[0][j + 1], dp[0][j]);
  68.         }
  69.         for (int i = 1; i < n; i++) {
  70.             dp【i】[0] = minAfter[i - 1][1] + costs【i】[0];
  71.             minPrior【i】[0] = dp【i】[0];
  72.             for (int j = 1; j < k - 1; j++) {
  73.                 dp【i】[j] = Math.min(minPrior[i - 1][j - 1], minAfter[i - 1][j + 1]) + costs【i】[j];
  74.                 minPrior【i】[j] = Math.min(minPrior【i】[j - 1], dp【i】[j]);
  75.             }
  76.             dp【i】[k - 1] = minPrior[i- 1][k - 2] + costs【i】[k - 1];// at first minPrior【i】[k - 2], make me crazy, cyb kill the bug
  77.             minPrior【i】[k - 1] = Math.min(minPrior【i】[k - 2], dp【i】[k - 1]);
  78.             minAfter【i】[k - 1] = dp【i】[k - 1];
  79.             for (int j = k - 2; j >= 0; j--) {
  80.                 minAfter【i】[j] = Math.min(minAfter【i】[j + 1], dp【i】[j]);
  81.             }
  82.         }
  83.         return minPrior[n - 1][k - 1];
  84.     }
  85. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表