There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an n x k cost matrix costs.
costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...Return the minimum cost to paint all houses.
Example 1:
Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.
Example 2:
Input: costs = [[1,3],[2,4]] Output: 5
Constraints:
costs.length == ncosts[i].length == k1 <= n <= 1002 <= k <= 201 <= costs[i][j] <= 20
Follow up: Could you solve it in O(nk) runtime?
Problem Overview: You are given n houses and k colors. Each costs[i][j] represents the cost of painting house i with color j. Adjacent houses cannot share the same color. The goal is to compute the minimum total cost to paint all houses while respecting this constraint.
Approach 1: Basic Dynamic Programming (O(n * k^2) time, O(k) space)
This approach builds the solution house by house using dynamic programming. For each house i and color j, you compute the cost as costs[i][j] + min(previous costs of all colors except j). That means iterating through all k colors from the previous row to find the minimum valid value. The DP state only needs the previous row, so space can be reduced to O(k). The downside is the nested scan over colors, giving O(n * k^2) time.
Approach 2: Optimized Dynamic Programming with Two Minimums (O(n * k) time, O(1) extra space)
The bottleneck in the previous approach is repeatedly searching for the minimum cost among k colors excluding the current one. Instead, track the smallest and second smallest values from the previous row. If the current color is different from the index of the smallest cost, use that value. Otherwise use the second smallest. This removes the inner loop and reduces each transition to constant time. You iterate through each house and each color once, resulting in O(n * k) time and O(1) extra space beyond the input.
The optimization works because every color only needs to know whether it conflicts with the global minimum from the previous step. If it conflicts, the second minimum is the next valid choice. This pattern appears frequently in array-based DP problems where transitions exclude a single index.
Recommended for interviews: Interviewers expect the optimized DP with two minimums. Starting with the O(n * k^2) dynamic programming formulation shows you understand the recurrence. Converting it to the O(n * k) solution demonstrates optimization skills and familiarity with dynamic programming state transitions. Most production-quality solutions use the optimized approach.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Dynamic Programming | O(n * k^2) | O(k) | Good starting point to understand the recurrence and constraints |
| Optimized DP with Two Minimums | O(n * k) | O(1) | Best solution for interviews and large k values |
Leetcode 265(hard). Paint House II【Array/Dynamic Programming】中文 • AndroidBabies安卓大宝贝们 • 873 views views
Watch 9 more video solutions →Practice Paint House II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor