Paint House II
Created: March 4, 2020 by [lek-tin]
Last updated: March 4, 2020
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.
Example
Input: [[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.
Solution (in-place top-down dp)
n: number of houses, k: number of colors
Time: O(n * k^2)
Space: O(1)
import math
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
N = len(costs)
if not costs or N==0:
return 0
K = len(costs[0])
for i in range(N-1, 0, -1):
for color in range(K):
minCost = math.inf
mins = [math.inf] * K
for j in range(K):
if j == color:
continue
minCost = min(minCost, costs[i][j])
costs[i-1][color] += minCost
minCost = math.inf
for c in costs[0]:
minCost = min(minCost, c)
return minCost
Solution (in-place down-up dp - optimized time)
n: number of houses, k: number of colors
Time: O(n * k)
Space: O(1)
import math
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
N = len(costs)
if not costs or N==0:
return 0
K = len(costs[0])
for i in range(1, N):
# min variables for the prev house
minColor, secondMinColor = None, None
for color in range(K):
cost = costs[i-1][color]
if minColor==None or cost<costs[i-1][minColor]:
secondMinColor = minColor
minColor = color
elif secondMinColor==None or cost<costs[i-1][secondMinColor]:
secondMinColor=color
for color in range(K):
if color==minColor:
costs[i][color] += costs[i-1][secondMinColor]
else:
costs[i][color] += costs[i-1][minColor]
# The min of the last house is the global min
return min(costs[-1])
Follow up
Could you solve it in O(nk) runtime?