Search
⌘K
Get Premium
Dynamic Programming
Paint House II
hard
Count: 10
DESCRIPTION (inspired by Leetcode.com)
You are a renowned painter who is given a task to paint n houses in a row. This time, you have k colors available. The cost of painting each house with each color is different and given in a 2D array costs:
- costs[i][j] = cost of painting house i with color j
No two neighboring houses can have the same color. Return the minimum cost to paint all houses.
Constraints:
- 1 ≤ n ≤ 100
- 1 ≤ k ≤ 20
- costs[i].length == k
- 1 ≤ costs[i][j] ≤ 1000
Follow-up: Can you solve this in O(n × k) time instead of the naive O(n × k²)?
Example 1
Input:
costs = [[4, 2, 8], [7, 1, 5], [3, 9, 6]]
Output:
8
Explanation:
- House 0: Color 0 (cost = 4)
- House 1: Color 1 (cost = 1)
- House 2: Color 0 (cost = 3)
- Total = 4 + 1 + 3 = 8
Example 2
Input:
costs = [[8, 3, 12, 5], [15, 9, 4, 7]]
Output:
7
Explanation: Paint house 0 with color 1 (cost = 3), house 1 with color 2 (cost = 4). Total = 7.
Explanation
Building Intuition
Approach 1: Direct Extension of Paint House
The Key Insight
Approach 2: Optimized DP with Min Tracking
Walkthrough
Solution
Why Not O(1) Space Like Paint House?
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