Paint House Ii - Leetcode Solution

Problem Description: 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.

Solution: This problem can be solved using dynamic programming. We start with the first house and try to find the minimum cost of painting all the houses in the row. For each house, we can paint it with one of the three colors: red, blue or green. We need to make sure that no two adjacent houses have the same color. So, if we paint the current house with red, the next house can be painted with either blue or green. In this way, we can form three color combinations for each house.

We can use a 2D array to keep track of the minimum cost of painting each house with a certain color. Let dp[i][j] be the minimum cost of painting houses from 0 to i, where the ith house is painted with color j. We can calculate this value using the following recurrence relation:

dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

The base case is when we are painting the first house. In that case, we can simply initialize the dp array with the costs for the first house. We then iterate through the array and calculate the minimum cost of painting all the houses. The answer will be the minimum value in the last row of the dp array.

Here is the Python code for this problem:

def minCostII(costs): if not costs: return 0

n = len(costs)
k = len(costs[0])

dp = [[0] * k for _ in range(n)]
dp[0] = costs[0]

for i in range(1, n):
    for j in range(k):
        dp[i][j] = costs[i][j] + min(dp[i-1][:j] + dp[i-1][j+1:])

return min(dp[-1])

We start by checking if the input matrix is empty. If it is, we return 0 since there are no houses to paint. We then initialize the variables n and k to the length of the input matrix and the number of colors respectively. We create a 2D array with n rows and k columns to keep track of the minimum cost of painting each house with a certain color. We initialize the first row of this array with the costs for the first house.

Next, we iterate through the array starting from the second row. For each house, we calculate the minimum cost of painting it with a certain color based on the costs for the previous houses. We then update the dp array with this value. Finally, we return the minimum value in the last row of the dp array, which represents the minimum cost of painting all the houses.

Time Complexity: The time complexity of this solution is O(nk^2), where n is the length of the input matrix and k is the number of colors. This is because we are iterating through the input matrix once and calculating the minimum value for each element in the dp array, which takes O(k) time. Since we are doing this for n elements, the total time complexity is O(nk^2).

Space Complexity: The space complexity of this solution is O(nk), where n is the length of the input matrix and k is the number of colors. This is because we are creating a 2D array with n rows and k columns to store the minimum cost of painting each house with a certain color. Therefore, the space required is O(nk).

1