O(n) Dynamic programming
IntuitionUse dynamic programming. Start from the two houses in the middle and find the minimum cost of painting them. Then at each step, add two more houses (on
# Intuition
Use dynamic programming. Start from the two houses in the middle and find the minimum cost of painting them. Then at each step, add two more houses (one on the left and one the right) and find the minimum cost of painting the two new houses in addition to all the previously examined houses.

# Approach
`dp[i][j][k]` is the minimum cost of painting houses from $$(n/2 - 1 - i)$$ to $$(n/2 + i)$$, using color $$j$$ for the house at $$(n/2 - 1 - 1)$$ and color $$k$$ for the house at $$(n/2 + i)$$.

So for $$i$$ == 0, `dp[0][j][k]` is the minimum cost of painting the two houses at $$(n/2 - 1)$$ and $$(n/2)$$, with color $$j$$ for the first house and color $$k$$ for the second house.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$
This can be reduced to $$O(1)$$ as we do not need to keep all the previous entries in the `dp` array

# Code
```java []
class Solution {
    public long minCost(int n, int[][] cost) {
        long[][][] dp = new long[n/2][3][3];

        for (int i=0; i<n/2; ++i) {
            for (int j=0; j<3; ++j) {
                for (int k=0; k<3; ++k) {
                    if (j == k) continue;
                    long minCost = findMinCost(dp, i, j, k, cost);
                    dp[n/2 - 1 - i][j][k] = minCost + cost[n/2 - 1 - i][j] + cost[n/2 + i][k];
                }
            }
        }               
        long res = Long.MAX_VALUE;
        for (int j=0; j<3; ++j) {
            for (int k=0; k<3; ++k) {
                if (j == k) continue;
                res = Math.min(res, dp[0][j][k]);
            }
        }
        return res;   
    }

    private long findMinCost(long[][][] dp, int i, int j, int k, int[][] cost) {
        if (i == 0)
            return 0;
        long mini = Long.MAX_VALUE;
        for (int a=0; a<3; ++a) {
            for (int b=0; b<3; ++b) {
                if (a == b || a == j || b == k) continue;
                mini = Math.min(mini, dp[n/2 - i][a][b]);
            }
        }
        return mini;
    }
}
```

Space optimized solution: $$O(1)$$
```
class Solution {
    public long minCost(int n, int[][] cost) {
        long[][] dpPrev = new long[3][3];
        long[][] dpNext = new long[3][3];
        for (int i=0; i<n/2; ++i) {
            for (int j=0; j<3; ++j) {
                for (int k=0; k<3; ++k) {
                    if (j == k) continue;
                    long minCost = findMinCost(dpPrev, i, j, k, cost);
                    dpNext[j][k] = minCost + cost[n/2 - 1 - i][j] + cost[n/2 + i][k];
                }
            }
            dpPrev = dpNext;
            dpNext = new long[3][3];
        }               
        long res = Long.MAX_VALUE;
        for (int j=0; j<3; ++j) {
            for (int k=0; k<3; ++k) {
                if (j == k) continue;
                res = Math.min(res, dpPrev[j][k]);
            }
        }
        return res;   
    }

    private long findMinCost(long[][] dpPrev, int i, int j, int k, int[][] cost) {
        if (i == 0)
            return 0;
        long mini = Long.MAX_VALUE;
        for (int a=0; a<3; ++a) {
            for (int b=0; b<3; ++b) {
                if (a == b || a == j || b == k) continue;
                mini = Math.min(mini, dpPrev[a][b]);
            }
        }
        return mini;
    }
}
```
['Dynamic Programming', 'Java']