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

LeetCode #256Medium
Grid DP · dp[i][c] = cost + min(other two colours)

Each house must be painted one of three 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 atAmazonMeta
step 1 / 18
3 houses × 3 colours · dp[i][c] = cheapest to paint houses 0..i ending colour c
·
·
·
·
·
·
·
·
·
Grid DP (tabulation)
▸
1dp = R × 3 grid
2dp[0] = costs[0]            // first house, no neighbour
3for i in 1..R−1: for c in 0..2:
4    dp[i][c] = costs[i][c] + min(dp[i−1][other two colours])
5 
6return min(dp[R−1])
state
  • costs row 0[17, 2, 17]
  • costs row 1[16, 16, 5]
  • costs row 2[14, 3, 19]
  • statedp[i][c] = cheapest, house i = colour c

line 1Paint each house one of three colours (R, G, B) so no two ADJACENT houses match, minimising total cost. STATE: dp[i][c] = the cheapest way to paint houses 0..i where house i is colour c. The answer is the smallest value in the bottom row.