[Leetcode] Paint House II

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 a n x k cost matrix. 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... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

This problem is similar to k-dimensional maximum weight path or house robber problem.

For maximum weight path / house robber problem, the recurrence relationship is:

dp[n] = min {input[n] + dp[n-2], dp[n-1]}

Here, if we define dp[r][c] as minimum cost when room r is painted with color c, then the recurrence relationship will be:

dp[r][c] = min{dp[r-1][l], l!=c} + costs[r][c]

Since we have n * k subproblems, and for each subproblem, we need to calculate min{dp[r-1][l], l!=c} which is a O(k) operation. So, the overall time complexity will be O(nk^2).

However, we really don't need to re-calculate minimum for every c, we only need to know the last two minimum numbers. If the room is not painted with color that comes with the minimum cost from previous rooms, then it should choose that color. In the case that we want to see that color, then the minimum cost up to now would be for previous room, we choose the second minimum cost.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution(object): def minCostII(self, costs): """ :type costs: List[List[int]] :rtype: int """ if not any(costs): return 0 n, k = len(costs), len(costs[0]) dp = [[0 for _ in range(k)] for _ in range(n)] dp[0] = costs[0] def helper(a): return min(a), a.index(min(a)) prev_cost_min, prev_min_color = helper(dp[0]) for r in range(1, n): for c in range(k): if c != prev_min_color: dp[r][c] = prev_cost_min + costs[r][c] else: tmp_cost = [dp[r-1][j] for j in range(c)+range(c+1, k)] dp[r][c] = min(tmp_cost) + costs[r][c] prev_cost_min, prev_min_color = helper(dp[r]) return prev_cost_min