Question

Formatted question description: https://leetcode.ca/all/256.html

 256	Paint House

 There are a row of n houses, each house can be painted with one of the three colors:
    red, blue or green.
 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 3 cost matrix.
 For example,
    costs[0][0] is the cost of painting house 0 with color red;
    costs[1][2] is the cost of painting house 1 with color green, and so on...

 Find the minimum cost to paint all houses.


 Example:

 Given costs = [[14,2,11],[11,14,5],[14,3,10]]
 return 10

 house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10


 Note:
 All costs are positive integers.

Algorithm

Two-dimensional dynamic array dp, where dp[i][j] represents the minimum cost of brushing to the i+1th house with color j, and the state transition equation is:

dp[i][j] = cost[i][j] + min(dp[i-1][(j + 1)% 3], dp[i-1][(j + 2)% 3])

Code

Java

public class Paint_House {

    public class Solution {
        public int minCost(int[][] costs) {
            int len = costs.length;

            if(costs != null && len == 0) {
                return 0;
            }

            int[][] dp = costs; // dp[i][j], for house-i, three colors j (0 or 1 or 2)

            // no need dp[m+1][n+1], just i=1 is good enough
            for(int i = 1; i < len; i++){
                dp[i][0] = costs[i][0] + Math.min(costs[i - 1][1], costs[i - 1][2]);
                dp[i][1] = costs[i][1] + Math.min(costs[i - 1][0], costs[i - 1][2]);
                dp[i][2] = costs[i][2] + Math.min(costs[i - 1][0], costs[i - 1][1]);
            }

            return Math.min(dp[len - 1][0], Math.min(dp[len - 1][1], dp[len - 1][2]));
        }
    }
}

// OJ: https://leetcode.com/problems/paint-house/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;
        for (int i = 1; i < costs.size(); ++i) {
            for (int j = 0; j < 3; ++j) costs[i][j] += min(costs[i - 1][(j + 1) % 3], costs[i - 1][(j + 2) % 3]);
        }
        return *min_element(costs.back().begin(), costs.back().end());
    }
};

class Solution(object):
  def minCost(self, costs):
    """
    :type costs: List[List[int]]
    :rtype: int
    """
    if not costs:
      return 0
    dp = [0] * (len(costs[0]))
    dp[:] = costs[0]
    for i in range(1, len(costs)):
      d0 = d1 = d2 = 0
      for j in range(0, 3):
        if j == 0:
          d0 = min(dp[1], dp[2]) + costs[i][0]
        elif j == 1:
          d1 = min(dp[0], dp[2]) + costs[i][1]
        else:
          d2 = min(dp[0], dp[1]) + costs[i][2]
      dp[0], dp[1], dp[2] = d0, d1, d2
    return min(dp)

256 - Paint House

Question

Algorithm

Code

All Problems

All Solutions