Paint House

Problem Statement

In this problem, we are tasked with painting a row of n houses, with a requirement that no two adjacent houses can be painted the same color. There are three possible colors to choose from—red, blue, or green—and each color has a different associated cost for each house. These costs are given in an n x 3 matrix named costs, where each row corresponds to a house and the entries in each row represent the cost of painting that house red, blue, or green, respectively.

The challenge is to determine the minimum cost required to paint all the houses meeting the above criteria. Each element in the matrix costs[i][j] stands for the cost of painting the i-th house with the j-th color where j corresponds to red, blue, and green colors.

Examples

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

Approach and Intuition

Given the restrictions and requirements of the problem, the naive approach would be extremely inefficient. We need a strategy that efficiently finds the minimum cost without redundantly recalculating for every possible scenario. Here is an intuitive approach to solve the problem using dynamic programming:

1. Initialization:

   • Start by creating a matrix (dp) that will store the minimum painting costs. dp[i][c] will represent the minimum cost to paint up to the i-th house, where the i-th house is painted with color c.

2. Base Case:

   • Initialize the first row of dp with the same values as the first row of costs because the first house can be painted independently with any of the three colors.

3. Fill the DP table:

   • For each subsequent house (i from 1 to n-1), calculate the cost of painting it with each of the three colors. Use the costs from the previous house to ensure no two adjacent houses are painted the same color.
   • For example, if deciding the cost of painting house i blue, you would take the minimum cost of painting the previous house either red or green, and add it to the cost of painting the current house blue.
   • Formally, for each color c for the i-th house:
     PYTHON

     Copy

     dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])  # Cost for painting i-th house RED
     dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])  # Cost for painting i-th house BLUE
     dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])  # Cost for painting i-th house GREEN

     Explain Code

     Powered by Vultr AgentBeta

4. Compute the Result:

   • After processing all houses, the last row of dp will contain the costs of painting all houses with each color fulfilling the problem's condition. The minimum of these values will be the result, which is the minimum cost to paint all houses such that no two adjacent houses have the same color.

By adhering to these steps, the problem leverages overlapping subproblems (common in dynamic programming scenarios) efficiently by building up the solution for the whole row of houses based on the solutions of smaller inputs (previous houses). This approach ensures that the problem is solved in a time complexity of O(n), which is efficient given the provided constraints.

Solutions

class Solution {
public:
    int calculateMinCost(vector<vector<int>>& expenses) {
        if (expenses.empty()) return 0;
    
        vector<int> lastRow = expenses.back();
    
        for (int i = expenses.size() - 2; i >= 0; --i) {
            vector<int> currentSpending = expenses[i];
    
            currentSpending[0] += min(lastRow[1], lastRow[2]);
            currentSpending[1] += min(lastRow[0], lastRow[2]);
            currentSpending[2] += min(lastRow[0], lastRow[1]);
    
            lastRow = currentSpending;
        }
    
        return min({lastRow[0], lastRow[1], lastRow[2]});
    }
};