Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Paint House II

LeetCode #265Hard
k colours · track the two smallest → O(n·k)

Each house must be painted one of k colors, and no two adjacent houses may share a color. Given the cost of painting each house each color, return the minimum total painting cost.

Asked atAmazon
step 1 / 21
2 houses × 3 colours · dp[i][c] = cheapest with house i = colour c
·
·
·
·
·
·
Naive · scan all other colours
▸
1dp[0] = costs[0]
2for i in 1..n−1:
3    for c in 0..k−1:
4        m = min(dp[i−1][c'] for c' != c)   // O(k) scan
5        dp[i][c] = costs[i][c] + m
6 
7return min(dp[n−1])
state
  • costs[0][1, 5, 3]
  • costs[1][2, 9, 4]
  • k3
  • statedp[i][c] = cheapest, house i = colour c

line 1Paint House with k colours: no two adjacent houses share a colour, minimise total cost. STATE: dp[i][c] = cheapest way to paint houses 0..i with house i in colour c, where dp[i][c] = costs[i][c] + min over every OTHER colour of dp[i−1].