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)
    
    

All Problems

All Solutions