[Dynamic Programming] Paint House - Medium

The Paint House problem is a well-known challenge in dynamic programming. The goal is to find the lowest cost to paint a line of houses. We have to use a limited number of colors. Also, we cannot paint two houses next to each other with the same color.

To solve this, we will calculate the best cost for each house. We base this on the colors used for the houses before it. This way, we can lower the total cost while following the color rules.

In this article, we will look at the Paint House problem closely. We will start with a clear overview of the problem and what we need to do. Then, we will go into different solutions. This includes a recursive method and a dynamic programming method in Java, Python, and C++. We will also talk about how to make our solutions use less space. Lastly, we will answer some common questions about the Paint House problem. Here are the topics we will cover:

  • Dynamic Programming Approach to Paint House Problem
  • Understanding the Paint House Problem Statement
  • Recursive Solution to Paint House Problem in Java
  • Dynamic Programming Solution to Paint House Problem in Java
  • Recursive Solution to Paint House Problem in Python
  • Dynamic Programming Solution to Paint House Problem in Python
  • Recursive Solution to Paint House Problem in C++
  • Dynamic Programming Solution to Paint House Problem in C++
  • Optimizing Space Complexity in Paint House Problem
  • Frequently Asked Questions

Understanding the Paint House Problem Statement

The Paint House problem is a well-known challenge in dynamic programming. We need to paint n houses using k different colors. We have to make sure that no two houses next to each other get the same color. Our aim is to keep the total cost of painting all houses as low as possible.

Problem Statement

  • We get an array called costs. In this array, costs[i][j] shows the cost to paint the i-th house with the j-th color.
  • We must ensure that two houses that are next to each other do not have the same color.
  • Our goal is to find the lowest cost to paint all the houses.

Constraints

  • 1 <= n <= 100 (this is the number of houses)
  • 1 <= k <= 20 (this is the number of colors)
  • 0 <= costs[i][j] <= 20 (this is the cost to paint)

Example

For example, look at this cost matrix for 3 houses and 3 colors:

costs = [
    [17, 2, 17],
    [16, 16, 5],
    [14, 3, 19]
]

Here, we can use dynamic programming to find the minimum cost to paint all houses. We will make sure that two adjacent houses do not have the same color. The aim is to calculate the least total cost while following the painting rules.

Recursive Solution to Paint House Problem in Java

The Paint House problem is about finding the least cost to paint many houses. We have a rule that no two houses next to each other can be painted the same color. We can solve this problem in a recursive way. We look at the cost to paint each house in different colors. Then, we calculate the costs for the next houses.

Problem Statement

We have n houses. Each house can be painted in one of k colors. The cost to paint the i-th house with the j-th color is in a 2D array called cost[n][k]. Our goal is to find the least cost to paint all the houses while following the rule about adjacent houses.

Recursive Approach

We can define the recursive solution like this:

  1. For each house, we check each color.
  2. For each color, we find the cost of painting the current house with that color. We then add this cost to the least cost we get from painting the next house with any color that is not the current one.

Java Implementation

public class PaintHouse {

    public int minCostRecursive(int[][] cost, int n, int color) {
        // Base case: If all houses are painted
        if (n < 0) {
            return 0;
        }

        int minCost = Integer.MAX_VALUE;

        // Check each color
        for (int c = 0; c < cost[0].length; c++) {
            // Make sure no two adjacent houses are the same color
            if (c != color) {
                // Calculate cost recursively
                int currentCost = cost[n][c] + minCostRecursive(cost, n - 1, c);
                minCost = Math.min(minCost, currentCost);
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        PaintHouse ph = new PaintHouse();
        int[][] cost = {
            {1, 2, 3},
            {10, 11, 12},
            {5, 6, 7}
        };
        int n = cost.length - 1; // Last house index
        int result = ph.minCostRecursive(cost, n, -1); // Start with no color
        System.out.println("Minimum cost to paint all houses: " + result);
    }
}

Explanation of the Code

  • The method minCostRecursive takes the cost matrix, the index of the house, and the last color used.
  • It uses recursion to check all possible color choices. It makes sure that adjacent houses are not the same color.
  • The base case gives 0 when there are no houses left to paint.
  • The main method sets up a sample cost matrix and calls the recursive method to find the least cost to paint.

This recursive method is simple but it can be slow for bigger inputs because it has overlapping problems. For better performance, we can think about using dynamic programming.

Dynamic Programming Solution to Paint House Problem in Java

The Paint House problem is a well-known problem in dynamic programming. The goal is to lower the cost of painting houses. We must ensure that no two houses next to each other have the same color. We have an array of costs. Each sub-array shows the cost of painting a house in different colors. We can use dynamic programming to find the least cost.

Problem Statement

We have n houses. Each house can be painted in one of k colors. The cost to paint the i-th house with the j-th color is in cost[i][j]. Our goal is to find the least cost to paint all houses. We must follow the rule that no two neighboring houses can have the same color.

Dynamic Programming Approach

  1. We define a DP array dp[i][j]. Here i is the house index and j is the color index.
  2. The formula we use is: [ dp[i][j] = cost[i][j] + _{m j}(dp[i-1][m]) ]
  3. We start by setting the costs of the first house from the cost array.
  4. We then go through all houses and colors to fill the DP table.
  5. The answer will be the smallest value in the last row of the DP table.

Java Code Implementation

public class PaintHouse {
    public static int minCost(int[][] cost) {
        if (cost == null || cost.length == 0 || cost[0].length == 0) {
            return 0;
        }
        
        int n = cost.length;
        int k = cost[0].length;
        
        int[][] dp = new int[n][k];
        
        // Set the first house's painting cost
        for (int j = 0; j < k; j++) {
            dp[0][j] = cost[0][j];
        }
        
        // Fill the DP table
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = cost[i][j] + Integer.MAX_VALUE;
                for (int m = 0; m < k; m++) {
                    if (m != j) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][m]);
                    }
                }
            }
        }
        
        // Find the least cost in the last row
        int minCost = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            minCost = Math.min(minCost, dp[n-1][j]);
        }
        
        return minCost;
    }
    
    public static void main(String[] args) {
        int[][] cost = {
            {1, 2, 3},
            {10, 11, 12},
            {7, 5, 8}
        };
        
        System.out.println("Minimum cost to paint all houses: " + minCost(cost));
    }
}

Explanation of the Code

  • The minCost function takes a 2D array cost as input.
  • It sets up the DP table and fills it based on our rules.
  • At the end, it finds and returns the least cost from the last row of the DP table.

This dynamic programming method finds the best solution for the paint house problem in Java. It makes sure we meet the rules while keeping the overall cost low.

For more about dynamic programming problems, we can check related topics like Dynamic Programming - Fibonacci Number or Dynamic Programming - Coin Change.

Recursive Solution to Paint House Problem in Python

The Paint House problem is a well-known challenge in dynamic programming. We want to paint n houses using k colors. We need to make sure that no two houses next to each other have the same color. Our goal is to keep the cost of painting all houses as low as possible.

Problem Statement:

We have an n x k cost matrix. In this matrix, cost[i][j] shows how much it costs to paint the i-th house with the j-th color. We need to find the lowest total cost to paint all the houses.

Recursive Approach:

In our recursive solution, we will try to paint each house with every color. We keep track of the last color used. This way, we can avoid painting two adjacent houses the same color.

Recursive Function:

def min_cost_rec(cost, n, k, house, last_color):
    if house == n:
        return 0
    
    min_cost = float('inf')
    for color in range(k):
        if color != last_color:
            current_cost = cost[house][color] + min_cost_rec(cost, n, k, house + 1, color)
            min_cost = min(min_cost, current_cost)
    
    return min_cost

Usage Example:

costs = [
    [1, 2, 3],
    [10, 11, 12],
    [7, 14, 5]
]
n = len(costs)
k = len(costs[0])
result = min_cost_rec(costs, n, k, 0, -1)
print(f"The minimum cost to paint all houses is: {result}")

Explanation:

  • Parameters:
    • cost: This is a 2D list of costs to paint.
    • n: This is the number of houses.
    • k: This is the number of colors.
    • house: This is the index of the house we are painting now.
    • last_color: This is the color of the last painted house.
  • Base Case: If we have painted all houses (house == n), we return 0.
  • Recursion: For each color, if it is different from last_color, we calculate the cost to paint the current house. Then we find the cost for the next house using recursion.

This recursive way is simple but can take a long time because of many repeated calculations. We can make it faster by using memoization or dynamic programming. We will talk about that in the next section.

For more information about dynamic programming, you can read about the Dynamic Programming - Fibonacci Number and Dynamic Programming - Climbing Stairs.

Dynamic Programming Solution to Paint House Problem in Python

We will solve the Paint House problem using dynamic programming in Python. Our aim is to reduce the total cost of painting houses. We must also make sure that no two neighboring houses have the same color. We can solve this problem well with a 2D dynamic programming table.

Problem Statement

We have n houses. Each house can be painted in one of three colors. Let’s call these colors 0, 1, and 2. The cost to paint each house with each color is in a 2D array called cost. The value cost[i][j] tells us the cost of painting the i-th house with color j. Our goal is to find the lowest cost to paint all the houses.

Dynamic Programming Approach

  1. Define the State: We define dp[i][j]. This value shows the minimum cost to paint the houses from 0 to i when we paint the i-th house with color j.

  2. State Transition: To update the costs, we use this formula:

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

    This way, we do not paint two neighboring houses with the same color.

  3. Base Case: For the first house, the cost is just the cost of painting it:

    dp[0][j] = cost[0][j] for j in range(3)

  4. Final Result: The lowest cost to paint all houses is:

    min(dp[n-1][0], dp[n-1][1], dp[n-1][2])

Implementation in Python

Here is the complete code for the dynamic programming solution to the Paint House problem in Python:

def min_cost_paint_houses(cost):
    if not cost:
        return 0
    
    n = len(cost)
    dp = [[0] * 3 for _ in range(n)]
    
    # Initialize the first house
    for j in range(3):
        dp[0][j] = cost[0][j]
    
    # Fill the dp array
    for i in range(1, n):
        for j in range(3):
            dp[i][j] = cost[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3])
    
    # Minimum cost to paint all houses
    return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])

# Example usage
cost = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
print(min_cost_paint_houses(cost))  # Output: 10

This code helps us find the minimum cost to paint all the houses while following the rules. The time complexity is O(n) and the space complexity is O(n), where n is the number of houses. If you want to learn more about similar dynamic programming problems, you can visit the Dynamic Programming - House Robber I.

Recursive Solution to Paint House Problem in C++

The Paint House problem needs us to paint n houses with k different colors. We must make sure that no two adjacent houses have the same color. Our goal is to lower the cost to paint all the houses.

Problem Statement

We have an integer array costs. Here, costs[i][j] shows the cost of painting the i-th house with the j-th color. We need to find the lowest cost to paint all the houses.

Recursive Approach

We calculate the lowest cost for every house based on what we chose for the previous house. We can make a recursive function that figures out the cost of painting the houses starting from the current index.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// Recursive function to find minimum cost
int paintHouseUtil(const vector<vector<int>>& costs, int houseIndex, int prevColor) {
    // Base case: all houses painted
    if (houseIndex == costs.size()) {
        return 0;
    }

    int minCost = INT_MAX;

    // Iterate through each color
    for (int color = 0; color < costs[0].size(); ++color) {
        // Skip if the color is the same as the previous house color
        if (color != prevColor) {
            int currentCost = costs[houseIndex][color] + paintHouseUtil(costs, houseIndex + 1, color);
            minCost = min(minCost, currentCost);
        }
    }

    return minCost;
}

// Main function to invoke the recursive solution
int paintHouse(const vector<vector<int>>& costs) {
    return paintHouseUtil(costs, 0, -1);
}

// Example usage
int main() {
    vector<vector<int>> costs = {
        {17, 2, 17},
        {16, 16, 5},
        {14, 3, 19}
    };
    
    cout << "Minimum cost to paint all houses: " << paintHouse(costs) << endl;
    return 0;
}

Explanation

  • The paintHouseUtil function takes the current house index and the last color used as inputs.
  • It checks if all houses are painted. If yes, it gives back 0.
  • For each color, it calculates the cost if we choose that color, skipping the previous color.
  • We update the minimum cost for each color choice.
  • The main function starts the recursive process and shows the minimum cost.

This recursive solution has an exponential time complexity of O(k^n). Here, n is the number of houses and k is the number of colors. We can make this approach faster using dynamic programming to lower the time complexity a lot. For faster solutions, we can look at the Dynamic Programming Solution to Paint House Problem in C++.

Dynamic Programming Solution to Paint House Problem in C++

The Paint House problem is a well-known challenge in dynamic programming. We have n houses in a line. Each house can be painted in one of k colors. The cost to paint each house in each color is in a cost matrix. We cannot paint two adjacent houses in the same color. Our goal is to lower the total cost of painting all the houses.

C++ Implementation

Here is how we can write the dynamic programming solution for the Paint House problem in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minCost(vector<vector<int>>& costs) {
    if (costs.empty()) return 0;

    int n = costs.size();
    int k = costs[0].size();

    // DP array to keep track of the minimum cost up to the current house
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            int minCost = INT_MAX;
            for (int l = 0; l < k; ++l) {
                if (j != l) {
                    minCost = min(minCost, costs[i-1][l]);
                }
            }
            costs[i][j] += minCost; // Add the minimum cost of the previous house
        }
    }

    // Find the minimum cost for the last house
    int result = INT_MAX;
    for (int j = 0; j < k; ++j) {
        result = min(result, costs[n-1][j]);
    }
    
    return result;
}

int main() {
    vector<vector<int>> costs = {
        {17, 2, 17},
        {16, 16, 5},
        {14, 3, 19}
    };
    cout << "Minimum cost to paint the houses: " << minCost(costs) << endl;
    return 0;
}

Explanation of the Code

  • Input: We use a 2D vector called costs. Here, costs[i][j] shows the cost to paint the i-th house with the j-th color.
  • Dynamic Programming Table: The algorithm calculates the minimum cost to paint each house. We make sure no two adjacent houses have the same color.
  • Final Calculation: After checking all houses, we find the minimum cost from the last house’s costs. This gives us the overall minimum cost.

This C++ solution works well for the Paint House problem using dynamic programming. It is efficient and follows the rules of the problem. If we want to practice more with dynamic programming, we can look at the House Robber problem or the Minimum Path Sum in a Grid.

Optimizing Space Complexity in Paint House Problem

We can make space usage better in the Paint House problem. This means we can use less memory for the dynamic programming method. Instead of keeping a 2D array for all the costs of each house and color, we can use a rolling array method. We only need costs from the last house to find the costs of the current house.

Space Optimization Technique

  1. Use of Two Variables: We do not need an array to keep costs for each color of the last house. We can just use two variables to store the minimum costs for the last house painted in different colors.

  2. Iterative Calculation: As we go through each house, we update the costs based on the last house’s costs. We do not need to save all old states.

Java Implementation

public class PaintHouse {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;

        int prevRed = costs[0][0];
        int prevGreen = costs[0][1];
        int prevBlue = costs[0][2];

        for (int i = 1; i < costs.length; i++) {
            int currentRed = costs[i][0] + Math.min(prevGreen, prevBlue);
            int currentGreen = costs[i][1] + Math.min(prevRed, prevBlue);
            int currentBlue = costs[i][2] + Math.min(prevRed, prevGreen);

            prevRed = currentRed;
            prevGreen = currentGreen;
            prevBlue = currentBlue;
        }

        return Math.min(prevRed, Math.min(prevGreen, prevBlue));
    }
}

Python Implementation

class PaintHouse:
    def minCost(self, costs):
        if not costs:
            return 0
        
        prev_red, prev_green, prev_blue = costs[0]
        
        for i in range(1, len(costs)):
            current_red = costs[i][0] + min(prev_green, prev_blue)
            current_green = costs[i][1] + min(prev_red, prev_blue)
            current_blue = costs[i][2] + min(prev_red, prev_green)

            prev_red, prev_green, prev_blue = current_red, current_green, current_blue

        return min(prev_red, prev_green, prev_blue)

C++ Implementation

class PaintHouse {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;

        int prevRed = costs[0][0], prevGreen = costs[0][1], prevBlue = costs[0][2];

        for (int i = 1; i < costs.size(); i++) {
            int currentRed = costs[i][0] + min(prevGreen, prevBlue);
            int currentGreen = costs[i][1] + min(prevRed, prevBlue);
            int currentBlue = costs[i][2] + min(prevRed, prevGreen);

            prevRed = currentRed;
            prevGreen = currentGreen;
            prevBlue = currentBlue;
        }

        return min(prevRed, min(prevGreen, prevBlue));
    }
};

By using this better way, we can lower the space complexity from O(n) to O(1). We only keep three variables no matter how many houses we have. This helps a lot when we have large inputs and still keeps the dynamic programming solution for the Paint House problem efficient. For more on dynamic programming methods, check the Dynamic Programming: House Robber I article.

Frequently Asked Questions

1. What is the Paint House problem in dynamic programming?

The Paint House problem is a well-known challenge in dynamic programming. The goal is to lower the cost of painting houses. Each house can be painted with different colors. But we can’t paint two adjacent houses the same color. We can solve this problem using recursive methods and dynamic programming. This helps us work better and avoid repeating work.

2. How does the dynamic programming approach work for the Paint House problem?

In the dynamic programming method for the Paint House problem, we create a table. This table keeps track of the lowest painting costs for each house based on what we chose for the previous house. By calculating costs step by step and saving the results, we do not repeat calculations. This gives us a good and fast solution. This way, we can find the best cost while following the color rules.

3. Can I implement the Paint House solution in Python?

Yes, we can implement the Paint House solution in Python. We can use both recursive and dynamic programming methods. The dynamic programming method works really well. It uses a 2D list to keep track of costs for painting each house in different colors. This helps us to quickly find the lowest cost while following the painting rules.

4. What are the time and space complexities of the Paint House problem?

The time complexity for the dynamic programming solution of the Paint House problem is O(nk). Here, n is the number of houses and k is the number of colors. The space complexity is also O(nk) because we store costs in a 2D array. But we can make it better to O(k) if we only keep the last two rows of the table.

5. Are there similar problems to the Paint House problem in dynamic programming?

Yes, there are many similar problems in dynamic programming. They have ideas like the Paint House problem. For example, the House Robber problem is about getting the most profit without setting off alarms when robbing nearby houses. We can look at this and other problems like Minimum Cost Climbing Stairs for practice and to learn more about dynamic programming. For more information, we can check out the House Robber I problem and the Minimum Cost Climbing Stairs article for more details.