Easy Approach
IntuitionUse dynamic programming to compute the minimum cost while ensuring no adjacent or equidistant houses have the same color.Approach
Initialize a 3D DP ar
# Intuition 
<!-- Describe your first thoughts on how to solve this problem. -->
Use dynamic programming to compute the minimum cost while ensuring no adjacent or equidistant houses have the same color.

# Approach
<!-- Describe your approach to solving the problem. -->
- Initialize a 3D DP array where dp[row][i][j] represents the minimum cost to paint up to row row with the current row painted color i and its equidistant counterpart painted color j.
- Iteratively update the DP array by considering all valid transitions from the previous row while checking constraints. The final answer is the minimum value in the last DP row.

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    typedef long long int ll;
    long long minCost(int n, vector<vector<int>>& cost) {
        // DP array to store the minimum cost of painting houses
        vector<vector<vector<ll>>> dp(n / 2, vector<vector<ll>>(3, vector<ll>(3, LLONG_MAX)));

        // Initialize the dp for the first pair (0th house and (n-1)th house)
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    dp[0][i][j] = cost[0][i] + cost[n-1][j];  // First and last house painted with i and j respectively
                }
            }
        }

        // DP calculation for subsequent houses
        for (int row = 1; row < n / 2; row++) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j) continue;  // Skip when adjacent houses are the same color
                    
                    ll minPrev = LLONG_MAX;
                    
                    // Search for previous valid (i1, j1) where i1 != i, j1 != j, and i1 != j1
                    for (int i1 = 0; i1 < 3; i1++) {
                        for (int j1 = 0; j1 < 3; j1++) {
                            if (i1 != i && j1 != j && i1 != j1) {
                                minPrev = min(minPrev, dp[row-1][i1][j1]);
                            }
                        }
                    }
                    
                    dp[row][i][j] = minPrev + cost[row][i] + cost[n-row-1][j];
                }
            }
        }

        // Final answer is the minimum cost from the last row dp[n/2 - 1] considering i != j
        ll result = LLONG_MAX;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    result = min(result, dp[n/2-1][i][j]);
                }
            }
        }

        return result;
    }
};
```
['C++']