hard20 pts · first answer countsdynamic-programmingdp-basicsspace-optimization

Painting houses with many colours fast

You paint n houses with k colours, no two neighbours the same, at minimum cost. The simple DP is O(n × k^2). How do you get O(n × k)?

A.Keep the smallest and second-smallest totals of the last houseB.Paint every house with its own single cheapest colour, greedilyC.Sort the colours by cost once at the start and reuse that orderD.Only try the first two colours for each house in the row

Discussion 0

Join free to post in the discussion.

Painting houses with many colours fast

Discussion 0

Related questions