State
dp[i][c] = min cost to paint first i houses, house i is color c.
Advertisement
Transition
dp[i][R] = cost[i][R] + min(dp[i-1][G], dp[i-1][B]);
dp[i][G] = cost[i][G] + min(dp[i-1][R], dp[i-1][B]);
dp[i][B] = cost[i][B] + min(dp[i-1][R], dp[i-1][G]);Advertisement
Answer
min(dp[n-1][R], dp[n-1][G], dp[n-1][B]). Whichever color the last house ends up as.
K colors extension
Track for each house: min1 and min2 (two smallest previous costs). Transition uses these. O(NK) instead of O(NK²).