Search
⌘K
Get Premium
Dynamic Programming
Paint House
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
You are a renowned painter who is given a task to paint n houses in a row. You can paint each house with one of three colors: Red, Blue, or Green. The cost of painting each house with each color is different and given in a 2D array costs:
- costs[i][0] = cost of painting house i Red
- costs[i][1] = cost of painting house i Blue
- costs[i][2] = cost of painting house i Green
No two neighboring houses can have the same color. Return the minimum cost to paint all houses.
Constraints:
- 1 ≤ n ≤ 100
- costs[i].length == 3
- 1 ≤ costs[i][j] ≤ 1000
Example 1
Input:
costs = [[8, 4, 15], [10, 7, 3], [6, 9, 12]]
Output:
13
Explanation:
- House 0: Blue (cost = 4)
- House 1: Green (cost = 3)
- House 2: Red (cost = 6)
- Total = 4 + 3 + 6 = 13
Example 2
Input:
costs = [[5, 8, 6], [19, 14, 13], [7, 5, 12], [14, 5, 9]]
Output:
30
Explanation: Red(5) → Green(13) → Red(7) → Blue(5) = 30
Explanation
Building Intuition
Approach 1: Brute Force (Try All Colorings)
The Problem: Overlapping Subproblems
Approach 2: Top-Down DP (Memoization)
Approach 3: Bottom-Up DP
The Recurrence
Walkthrough
Space Optimization
Solution
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Unlock Premium Coding Content
Reading Progress
On This Page