Paint House | Dynamic Programming | Hello Interview

You have a row of houses. Each one can be painted red, blue, or green, with a different cost per house. The constraint: no two neighboring houses can share the same color. Find the minimum total cost to paint them all. Brute force tries every combination. With three colors and n houses, that's 3^n possibilities. That doesn't scale. DP fixes this with one key insight: you don't need to track the full sequence of colors. At each house, you only need to know the cheapest way to paint it each color given what came before. So you carry three values forward as you move through the row — the minimum cost to reach the current house painted red, blue, or green. For each new house, painting it red means the previous house can't be red, so you add the red cost to the cheaper of the previous blue and green. Same logic for each color. By the last house, you've got three numbers. The smallest one is your answer. O(n) time. Constant space if you update in place. In this video we cover: • Why brute force explodes and where DP comes in • How to define the state and the recurrence relation • Walking through the transitions step by step • The space optimization from O(n) to O(1) • The broader DP pattern: figure out the minimum state you actually need to carry forward — it's almost always smaller than you think Practice Paint House and hundreds of other problems at hellointerview.com. ——— Tags: paint house leetcode, dynamic programming interview, DP minimum cost, coding interview prep, leetcode medium, dynamic programming explained, technical interview practice, hellointerview #shorts