---
title: 'Paint House | Dynamic Programming | Hello Interview'
source: 'https://youtube.com/watch?v=XNzXB5cAE_s'
video_id: 'XNzXB5cAE_s'
date: 2026-08-04
duration_sec: 78
---

# Paint House | Dynamic Programming | Hello Interview

> Source: [Paint House | Dynamic Programming | Hello Interview](https://youtube.com/watch?v=XNzXB5cAE_s)

## Summary

This video from Hello Interview explains the classic 'Paint House' dynamic programming problem. It presents a simple rule for painting a row of houses with three colors, where no two adjacent houses can share a color, and demonstrates how to find the minimum cost using a DP approach. The video walks through the core recurrence and traces a solution, highlighting the efficiency of dynamic programming over brute force.

### Key Points

- **Problem Statement** [00:01] — You have a row of houses to paint, each can be red, blue, or green, with different costs per house. Constraint: no two neighbors can share a color. Goal: find the cheapest way to paint all houses.
- **Brute Force Infeasibility** [00:13] — Naive approach is 3^n, which is exponential and 'dead on arrival' for large n.
- **Core DP Recurrence** [00:27] — For each house, compute the best total cost if painted red, blue, or green. For red: take the cheaper of the previous house's blue or green totals and add today's red cost. Similarly for blue and green.
- **Tracing the Solution** [00:41] — Initialize DP grid with first row as costs. For second row, green is best with cost 7. For last row, blue is best with cost 10. Each row only needs one space, demonstrating space optimization.
- **Space Optimization Challenge** [01:07] — The video poses a question: how to optimize space from linear to constant? Encourages comments and mentions interactive visualizations at Hello Interview.

### Conclusion

The Paint House problem is a classic example of dynamic programming, where the optimal solution is built by considering the best cost for each color at each house, leading to an efficient O(n) time solution. The video effectively demonstrates the recurrence and invites further exploration of space optimization.

## Transcript

is because it's really just one simple rule. You've got a row of houses to paint. Each one can be red, blue, or green. And each color has a different price at each house. The catch is that no two neighbors can
share a color. So, what's the cheapest way to paint them all? coloring. That's three to the end, which is dead on arrival. Instead, you need to the cheapest way to paint this house red?" Well, the house before it had to
cheaper of those two running totals and add today's red cost. Same for blue and green. That's the whole trick. Now, for every house, you build three answers. What's the best total cost if this house is red? Best total cost if
this house is blue? And the best total cost if this house is green? Let's trace the solution. Initialize your DP grid. The first row is just the costs. Green is the best choice for the second row with a cost of seven. For the
last row, blue is the best choice with a cost of 10. Each row only needs the one space. That's dynamic programming. You're not building the cheapest valid answer one house at a time. Well, here's a fun
optimize the space even further from linear to constant? Comment your answers below. And learn more with interactive visualizations at Hello Interview.