Paint House IV
MediumUpdated: Jul 26, 2025
Practice on:
Problem
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.
Examples
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 <= 10^5nis even.cost.length == ncost[i].length == 30 <= cost[i][j] <= 10^5
Solution
Method 1 – Dynamic Programming with State Compression
Intuition
The problem requires painting each house with one of three colors such that no two adjacent houses and no two houses equidistant from the ends have the same color. The key is to use dynamic programming, tracking the last color and the color of the equidistant house, and rolling the DP to save space.
Approach
- Use a DP table where
dp[pc][ec]is the minimum cost to paint up to the current house, with previous colorpcand equidistant colorec. - For each house, try all color choices, skipping those that violate adjacency or equidistant constraints.
- Use rolling arrays to keep only the last state.
- The answer is the minimum value in the DP table after processing all houses.
Code
C++
class Solution {
public:
int minCost(vector<vector<int>>& cost) {
int n = cost.size();
vector<vector<int>> dp(3, vector<int>(3, 1e9));
for (int c = 0; c < 3; ++c) dp[c][c] = cost[0][c];
for (int i = 1; i < n; ++i) {
vector<vector<int>> ndp(3, vector<int>(3, 1e9));
for (int pc = 0; pc < 3; ++pc) {
for (int ec = 0; ec < 3; ++ec) {
for (int c = 0; c < 3; ++c) {
if (c == pc) continue;
int eq = ec;
if (i >= n/2) {
if (n-1-i < n/2) eq = c;
if (c == eq) continue;
}
ndp[c][eq] = min(ndp[c][eq], dp[pc][ec] + cost[i][c]);
}
}
}
dp = ndp;
}
int ans = 1e9;
for (int pc = 0; pc < 3; ++pc)
for (int ec = 0; ec < 3; ++ec)
ans = min(ans, dp[pc][ec]);
return ans;
}
};
Go
func minCost(cost [][]int) int {
n := len(cost)
dp := make([][]int, 3)
for i := range dp {
dp[i] = make([]int, 3)
for j := range dp[i] { dp[i][j] = 1e9 }
}
for c := 0; c < 3; c++ { dp[c][c] = cost[0][c] }
for i := 1; i < n; i++ {
ndp := make([][]int, 3)
for k := range ndp {
ndp[k] = make([]int, 3)
for l := range ndp[k] { ndp[k][l] = 1e9 }
}
for pc := 0; pc < 3; pc++ {
for ec := 0; ec < 3; ec++ {
for c := 0; c < 3; c++ {
if c == pc { continue }
eq := ec
if i >= n/2 {
if n-1-i < n/2 { eq = c }
if c == eq { continue }
}
ndp[c][eq] = min(ndp[c][eq], dp[pc][ec]+cost[i][c])
}
}
}
dp = ndp
}
ans := 1e9
for pc := 0; pc < 3; pc++ {
for ec := 0; ec < 3; ec++ {
if dp[pc][ec] < ans { ans = dp[pc][ec] }
}
}
return ans
}
func min(a, b int) int { if a < b { return a }; return b }
Java
class Solution {
public int minCost(int[][] cost) {
int n = cost.length;
int[][] dp = new int[3][3];
for (int[] row : dp) Arrays.fill(row, (int)1e9);
for (int c = 0; c < 3; c++) dp[c][c] = cost[0][c];
for (int i = 1; i < n; i++) {
int[][] ndp = new int[3][3];
for (int[] row : ndp) Arrays.fill(row, (int)1e9);
for (int pc = 0; pc < 3; pc++) {
for (int ec = 0; ec < 3; ec++) {
for (int c = 0; c < 3; c++) {
if (c == pc) continue;
int eq = ec;
if (i >= n/2) {
if (n-1-i < n/2) eq = c;
if (c == eq) continue;
}
ndp[c][eq] = Math.min(ndp[c][eq], dp[pc][ec] + cost[i][c]);
}
}
}
dp = ndp;
}
int ans = (int)1e9;
for (int pc = 0; pc < 3; pc++)
for (int ec = 0; ec < 3; ec++)
ans = Math.min(ans, dp[pc][ec]);
return ans;
}
}
Kotlin
class Solution {
fun minCost(cost: Array<IntArray>): Int {
val n = cost.size
var dp = Array(3) { IntArray(3) { 1_000_000_000 } }
for (c in 0..2) dp[c][c] = cost[0][c]
for (i in 1 until n) {
val ndp = Array(3) { IntArray(3) { 1_000_000_000 } }
for (pc in 0..2) {
for (ec in 0..2) {
for (c in 0..2) {
if (c == pc) continue
var eq = ec
if (i >= n/2) {
if (n-1-i < n/2) eq = c
if (c == eq) continue
}
ndp[c][eq] = minOf(ndp[c][eq], dp[pc][ec] + cost[i][c])
}
}
}
dp = ndp
}
var ans = 1_000_000_000
for (pc in 0..2)
for (ec in 0..2)
ans = minOf(ans, dp[pc][ec])
return ans
}
}
Python
class Solution:
def minCost(self, cost: list[list[int]]) -> int:
n = len(cost)
dp: list[list[float]] = [[float('inf')]*3 for _ in range(3)]
for c in range(3):
dp[c][c] = cost[0][c]
for i in range(1, n):
ndp: list[list[float]] = [[float('inf')]*3 for _ in range(3)]
for pc in range(3):
for ec in range(3):
for c in range(3):
if c == pc: continue
eq = ec
if i >= n//2:
if n-1-i < n//2: eq = c
if c == eq: continue
ndp[c][eq] = min(ndp[c][eq], dp[pc][ec] + cost[i][c])
dp = ndp
return int(min(min(row) for row in dp))
Rust
impl Solution {
pub fn min_cost(cost: Vec<Vec<i32>>) -> i32 {
let n = cost.len();
let mut dp = vec![vec![i32::MAX/2; 3]; 3];
for c in 0..3 { dp[c][c] = cost[0][c]; }
for i in 1..n {
let mut ndp = vec![vec![i32::MAX/2; 3]; 3];
for pc in 0..3 {
for ec in 0..3 {
for c in 0..3 {
if c == pc { continue; }
let mut eq = ec;
if i >= n/2 {
if n-1-i < n/2 { eq = c; }
if c == eq { continue; }
}
ndp[c][eq] = ndp[c][eq].min(dp[pc][ec] + cost[i][c]);
}
}
}
dp = ndp;
}
dp.into_iter().flatten().min().unwrap()
}
}
TypeScript
class Solution {
minCost(cost: number[][]): number {
const n = cost.length;
let dp: number[][] = Array.from({length: 3}, () => Array(3).fill(Infinity));
for (let c = 0; c < 3; c++) dp[c][c] = cost[0][c];
for (let i = 1; i < n; i++) {
const ndp: number[][] = Array.from({length: 3}, () => Array(3).fill(Infinity));
for (let pc = 0; pc < 3; pc++) {
for (let ec = 0; ec < 3; ec++) {
for (let c = 0; c < 3; c++) {
if (c === pc) continue;
let eq = ec;
if (i >= n/2) {
if (n-1-i < n/2) eq = c;
if (c === eq) continue;
}
ndp[c][eq] = Math.min(ndp[c][eq], dp[pc][ec] + cost[i][c]);
}
}
}
dp = ndp;
}
return Math.min(...dp.flat());
}
}
Complexity
- ⏰ Time complexity:
O(n), where n is the number of houses. For each house, we try all color combinations (constant work for each house). - 🧺 Space complexity:
O(1), since we only keep a 3x3 DP table for rolling states.