With recursion and memo-O(n) Time and Space complexity.
IntuitionWithin commentsApproachWithin commentsComplexity

Time complexity:
O(n)


Space complexity:
O(n)

Code
# Intuition
Within comments

# Approach
Within comments

# Complexity
- Time complexity:
O(n) 

- Space complexity:
O(n) 

# Code
```java []
class Solution {
    int houses; // Total number of houses
    long[][][] dp; // 3D DP array for memoization

    /**
     * Recursive method to calculate the minimum cost.
     * 
     * @param cost 2D array where cost[i][j] represents the cost of painting house `i` with color `j`.
     * @param prevColor The color used for the previous house (-1 if none).
     * @param currentHouse The current house being painted.
     * @param frontColor The color used for the corresponding symmetric house (-1 if none).
     * @return The minimum cost to paint all houses starting from the currentHouse.
     */
    public long solve(int[][] cost, int prevColor, int currentHouse, int frontColor) {
        // Base case: if all houses on one side are painted
        if (currentHouse == houses / 2) {
            return 0; // No more cost required
        }

        // Check if the result is already computed
        if (dp[currentHouse][prevColor + 1][frontColor + 1] != -1) {
            return dp[currentHouse][prevColor + 1][frontColor + 1];
        }

        long take = Long.MAX_VALUE; // Initialize to a large value (to find the minimum)

        int equiHouse = houses - currentHouse - 1; // Symmetric house index
        // Iterate over possible colors for the current house
        for (int i = 0; i < 3; i++) {
            if (i == prevColor) { // Avoid using the same color as the previous house
                continue;
            }
            // Iterate over possible colors for the symmetric house
            for (int j = 0; j < 3; j++) {
                if (i == j || j == frontColor) { // Ensure different colors for current and symmetric houses
                    continue;
                }
                // Recursive call for the next house
                take = Math.min(take, 
                    cost[currentHouse][i] + cost[equiHouse][j] + solve(cost, i, currentHouse + 1, j));
            }
        }

        // Store the result in the DP table and return it
        return dp[currentHouse][prevColor + 1][frontColor + 1] = take;
    }

    /**
     * Method to calculate the minimum cost of painting all houses.
     * 
     * @param n Total number of houses.
     * @param cost 2D array where cost[i][j] is the cost of painting house `i` with color `j`.
     * @return The minimum cost of painting all houses with given constraints.
     */
    public long minCost(int n, int[][] cost) {
        houses = n; // Store total number of houses
        dp = new long[n / 2 + 1][4][4]; // DP table dimensions: [currentHouse][prevColor + 1][frontColor + 1]
        
        // Initialize DP table with -1 (uncomputed states)
        for (int i = 0; i < n / 2 + 1; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        // Start solving from house 0 with no previous or front color
        return solve(cost, -1, 0, -1);
    }
}

```
['Java']