Welcome to Subscribe On Youtube

256. Paint House

Description

There is a row of n houses, where each house can be painted one of 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 an n x 3 cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

 

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

 

Constraints:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

Solutions

Explanation of the Solution:

• Initialization: Three variables a, b, and c are initialized to 0. These variables will hold the cumulative minimum costs of painting up to the current house, ending with each of the three colors respectively.

• Iteration Over Houses: The code iterates over each house’s painting costs. For each house, represented by its costs [ca, cb, cc] for painting it with colors 0, 1, and 2 respectively:
  • The new value of a is set to the minimum of the previous values of b and c added to ca. This represents the minimum cost of painting the current house with color 0, given that the previous house was painted with color 1 or 2.
  • Similarly, the new value of b is set to the minimum of the previous values of a and c added to cb, representing painting the current house with color 1.
  • The new value of c is set to the minimum of the previous values of a and b added to cc, representing painting the current house with color 2.
• Finding the Minimum Total Cost: After iterating through all the houses, the minimum of a, b, and c gives the overall minimum cost to paint all houses following the rule that no two adjacent houses are painted with the same color.

Why It Works:

This dynamic programming approach works because, at each step (for each house), it considers the minimum cost incurred so far for each color choice, ensuring that no two adjacent houses are painted the same color by switching to a different color for the current house. By cumulatively building up the solution from the base (starting with 0 cost and adding the house costs one by one), it finds the global minimum cost to paint all houses under the given constraints.

Example:

Given costs = [[17,2,17],[16,16,5],[14,3,19]], the function will calculate as follows:

• After the first house, the costs are [17, 2, 17].
• For the second house, it calculates the new costs as [18 (2+16), 5 (2+3), 7 (2+5)].
• For the third house, the costs are updated to [19, 10, 14].
• The minimum cost to paint all houses will be min(19, 10, 14) = 10.

• Java
• C++
• Python
• Go
• Javascript

• class Solution {
      public int minCost(int[][] costs) {
          int r = 0, g = 0, b = 0;
          for (int[] cost : costs) {
              int _r = r, _g = g, _b = b;
              r = Math.min(_g, _b) + cost[0];
              g = Math.min(_r, _b) + cost[1];
              b = Math.min(_r, _g) + cost[2];
          }
          return Math.min(r, Math.min(g, b));
      }
  }
  
  

• class Solution {
  public:
      int minCost(vector<vector<int>>& costs) {
          int r = 0, g = 0, b = 0;
          for (auto& cost : costs) {
              int _r = r, _g = g, _b = b;
              r = min(_g, _b) + cost[0];
              g = min(_r, _b) + cost[1];
              b = min(_r, _g) + cost[2];
          }
          return min(r, min(g, b));
      }
  };
  
  

• class Solution:
      def minCost(self, costs: List[List[int]]) -> int:
          a = b = c = 0
          for ca, cb, cc in costs:
              a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc
          return min(a, b, c)
  
  ##############
  
  '''
  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])
  
  '''
  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)
  
  
  

• func minCost(costs [][]int) int {
  	r, g, b := 0, 0, 0
  	for _, cost := range costs {
  		_r, _g, _b := r, g, b
  		r = min(_g, _b) + cost[0]
  		g = min(_r, _b) + cost[1]
  		b = min(_r, _g) + cost[2]
  	}
  	return min(r, min(g, b))
  }
  

• /**
   * @param {number[][]} costs
   * @return {number}
   */
  var minCost = function (costs) {
      let [a, b, c] = [0, 0, 0];
      for (let [ca, cb, cc] of costs) {
          [a, b, c] = [Math.min(b, c) + ca, Math.min(a, c) + cb, Math.min(a, b) + cc];
      }
      return Math.min(a, b, c);
  };
  
  

All Problems

All Solutions