Paint House - Leetcode Solution

Paint House is a dynamic programming problem on Leetcode that requires finding the minimum cost of painting n houses with k colors. Each house can be painted with one color from the available k colors. However, no two neighboring houses can be painted with the same color. The problem statement asks to determine the minimum cost required to paint all houses under these constraints.

Problem statement:

There are a row of n houses, each house can be painted with one of the k colors. 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 every house with a particular color is represented by a n x k cost matrix. For example, costs[0][0] represents the cost of painting house 0 with color 0; costs[1][2] represents the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Example:

Input: [[17, 2, 6], [16, 2, 8], [14, 2, 11]]

Output: 7

Explanation: Paint house 0 in color 1 (cost = 2), paint house 1 in color 2 (cost = 8), and paint house 2 in color 0 (cost = 14). Total cost = 2 + 8 + 14 = 24. However, the adjacent houses cannot have the same color. So, paint house 0 in color 1 (cost = 2), paint house 1 in color 0 (cost = 16), and paint house 2 in color 1 (cost = 2). Total cost = 2 + 16 + 2 = 20, which is the minimum cost.

Approach:

The problem can be solved using dynamic programming (DP) approach. First, we create a 2D DP array of size n x k, where DP[i][j] represents the minimum cost of painting house i with color j. For the base case, we assign the minimum cost of painting the first house with each color in the DP array.

Next, for each house from 1 to n-1, we loop through all k colors and for each color j, we calculate the minimum cost of painting the current house with color j plus the minimum cost of painting the previous house with any color other than j. We update the DP array with the minimum cost of painting the current house with color j.

Finally, we loop through the last row of the DP array to find the minimum cost of painting the last house. This will be our final answer.

Pseudo code:

Let costs be the n x k cost matrix

Initialize the DP array, DP[n][k] to be filled with 0s:

for i in range(k): DP[0][i] = costs[0][i]

for i in range(1, n): for j in range(k): minCost = infinity for x in range(k): if x != j: minCost = min(minCost, DP[i-1][x]) DP[i][j] = costs[i][j] + minCost

minCost = infinity for i in range(k): minCost = min(minCost, DP[n-1][i]) return minCost

Time Complexity:

The time complexity of this approach is O(nk^2) as we loop through n houses and for each house, we loop through k colors and perform an inner loop of k iterations to calculate the minimum cost of painting the previous house with any color other than j.

Space Complexity:

The space complexity of this approach is O(nk) as we create a 2D DP array of size n x k to store the minimum costs of painting each house with each color.

1