3429. Paint House IV | 2 Way DP | Top Down DP
Paint House IV - Video Solution
Watch 3 video solutions for Paint House IV, a medium level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 2,998 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cost of size n x 3, where cost[i][j] represents the cost of painting house i with color j + 1.
The houses will look beautiful if they satisfy the following conditions:
- No two adjacent houses are painted the same color.
- Houses equidistant from the ends of the row are not painted the same color. For example, if
n = 6, houses at positions(0, 5),(1, 4), and(2, 3)are considered equidistant.
Return the minimum cost to paint the houses such that they look beautiful.
Example 1:
Input: n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]
Output: 9
Explanation:
The optimal painting sequence is [1, 2, 3, 2] with corresponding costs [3, 2, 1, 3]. This satisfies the following conditions:
- No adjacent houses have the same color.
- Houses at positions 0 and 3 (equidistant from the ends) are not painted the same color
(1 != 2). - Houses at positions 1 and 2 (equidistant from the ends) are not painted the same color
(2 != 3).
The minimum cost to paint the houses so that they look beautiful is 3 + 2 + 1 + 3 = 9.
Example 2:
Input: n = 6, cost = [[2,4,6],[5,3,8],[7,1,9],[4,6,2],[3,5,7],[8,2,4]]
Output: 18
Explanation:
The optimal painting sequence is [1, 3, 2, 3, 1, 2] with corresponding costs [2, 8, 1, 2, 3, 2]. This satisfies the following conditions:
- No adjacent houses have the same color.
- Houses at positions 0 and 5 (equidistant from the ends) are not painted the same color
(1 != 2). - Houses at positions 1 and 4 (equidistant from the ends) are not painted the same color
(3 != 1). - Houses at positions 2 and 3 (equidistant from the ends) are not painted the same color
(2 != 3).
The minimum cost to paint the houses so that they look beautiful is 2 + 8 + 1 + 2 + 3 + 2 = 18.
Constraints:
2 <= n <= 105nis even.cost.length == ncost[i].length == 30 <= cost[i][j] <= 105
Approach Overview
Problem Overview: You are given painting costs for n houses and three colors. Adjacent houses cannot share the same color, and houses that are symmetric from the start and end of the street must also have different colors. The goal is to minimize the total painting cost while satisfying both constraints.
Approach 1: Brute Force Backtracking (Exponential Time)
Try every possible color assignment for each house while enforcing the constraints during recursion. For each position, iterate through the three colors and skip any that match the previous house or its mirrored counterpart. This generates up to 3^n combinations, making it impractical for large inputs. Time complexity is O(3^n) and space complexity is O(n) from the recursion stack. This approach mainly helps validate the constraints before designing a dynamic programming solution.
Approach 2: Memoized Dynamic Programming (Top-Down)
Convert the brute force recursion into a DP by caching states. A useful state is the pair of houses processed from both ends. Track the color used for the previous pair and recursively compute the minimum cost for the next pair. Each state represents combinations of left and right colors, which is at most 3 × 3. Memoization prevents recomputation and reduces the complexity dramatically. Time complexity becomes roughly O(n × 9 × 9) and space complexity is O(n × 9) for memo storage. This approach demonstrates how dynamic programming eliminates exponential branching.
Approach 3: Bottom-Up Pair DP (Optimal)
Process houses from both ends simultaneously. At step i, consider the pair (i, n-1-i). Try all color combinations (c1, c2) for the pair where c1 != c2 to satisfy the mirror constraint. Also ensure c1 differs from the previous left color and c2 differs from the previous right color to satisfy adjacency. Maintain a DP table of size 3 × 3 representing the last chosen colors for the previous pair. For each new pair, iterate over all valid transitions and update the minimum cost. Because the color space is constant, each step performs a fixed number of operations.
The algorithm runs in O(n) time with O(1) extra space (only a small DP table). The input is handled as an array of costs, while the transitions rely on classic DP state transitions. The key insight is reducing the global mirror constraint into pairwise decisions processed from both ends.
Recommended for interviews: The bottom-up dynamic programming solution. Interviewers expect you to recognize the repeating structure and compress the state to color pairs. Mentioning the brute force first shows you understand the constraints, while the optimized DP demonstrates the ability to convert exponential recursion into a linear-time solution.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(3^n) | O(n) | Understanding constraints or validating small test cases |
| Memoized DP (Top-Down) | O(n × 9 × 9) | O(n × 9) | When converting recursion to DP while keeping code intuitive |
| Bottom-Up Pair DP | O(n) | O(1) | Optimal approach for interviews and production solutions |