LC: 265. Paint House II - spiralgo/algorithms GitHub Wiki

265. Paint House II:

The Essence:

It is clearly a DP problem as we can use previous cost data to decide the result for the future iterations.

It is a generalized variation of https://github.com/spiralgo/algorithms/issues/44.

Details:

If we had just 3 colors:

  costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);

We are accumulating the cost of the second previous minimum for an index here. We use "the second" because we do not want "two adjacent houses have the same color". When we had 3 alternative colors, we could utilize "Math.min" to decide the second previous minimum. But when we have k alternative colors, we have to iterate through the colors to keep the state of: preMin (previous minimum), preSecondMin (previous second minimum) , preMinIdx (the index of previous color with the minimum cost)

Detailed explanation and implementation: https://github.com/spiralgo/algorithms/pull/298