Paint House Iii - Leetcode Solution

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 each house with a certain color is represented by an n x k cost matrix costs.

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

Return the minimum cost to paint all houses.

Note: All costs are positive integers. Example 1:

Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. Example 2:

Input: costs = [[1,3],[2,4]] Output: 5

Approach:

The approach to solve this problem is Dynamic Programming. We will create a dp matrix which will store the minimum cost of painting the ith house with the jth color. We know that no two adjacent houses can have the same color. Hence, at the time of computing the minimum cost of painting the ith house with the jth color, we will check the minimum cost of painting the i-1th house with colors other than jth color.

Algorithm:

1. Create a dp matrix of size n x k, where n is the number of houses and k is the number of colors.
2. Initialize the first row of the dp matrix with the respective costs of painting the first house with each color.
3. Iterate from the second house to the last house.
4. For each house, iterate through all the colors.
5. For each color, compute dp[i][j] as the cost of painting the ith house with the jth color plus the minimum cost of painting the i-1th house with colors other than jth color.
6. Return the minimum value from the last row of the dp matrix.

Code:

Time Complexity: O(nk^2) Space Complexity: O(nk)

1