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.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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^5
  • n is even.
  • cost.length == n
  • cost[i].length == 3
  • 0 <= cost[i][j] <= 10^5

Examples

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

  1. Use a DP table where dp[pc][ec] is the minimum cost to paint up to the current house, with previous color pc and equidistant color ec.
  2. For each house, try all color choices, skipping those that violate adjacency or equidistant constraints.
  3. Use rolling arrays to keep only the last state.
  4. The answer is the minimum value in the DP table after processing all houses.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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.