256_Paint House
256. Paint House
Level: easy
Tag: dynamic programming
Question
Idea: dynamic programming, bottom-up
Start from the first house, there are three possibilities:
paint in first color, then the previous house must be paint in one of the other two colors which gives smallest cost.
paint in second color, then the previous house must be paint in one of the other two colors which gives smallest cost.
paint in third color, then the previous house must be paint in one of the other two colors which gives smallest cost.
Solution: can be easily generated to more than 3 colors
Time:
Space:
Last updated