16 Lines | C++ | Easy Solution | Memoization DP
IntuitionThe problem requires us to minimize the cost of painting n houses with 3 colors, under certain constraints:
No two adjacent houses can be painted the s
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to minimize the cost of painting `n` houses with 3 colors, under certain constraints:

1. No two adjacent houses can be painted the same color.
2. Houses that are equidistant from the ends must not be painted the same color.

The key here is to observe that since there are only 3 color choices for each house, this creates a small number of possible states per house, making dynamic programming (DP) an efficient solution.

# Approach
<!-- Describe your approach to solving the problem. -->
We can define a recursive function that computes the minimum cost of painting the houses starting from a given index `idx` with two restrictions: the colors of the previous house (`left`) and the last house (`right`). By memoizing these values using a DP table, we can avoid recomputing the same subproblem multiple times.

The idea is to try all possible combinations of colors for each house and select the minimum cost, while ensuring that the conditions (no adjacent houses with the same color, and no houses equidistant from the ends with the same color) are satisfied.

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

```cpp
class Solution {
public:
    long long dp[100001][4][4];  // DP table to store results for (index, left color, right color)
    long long helper(int left, int right, int idx, int n, vector<vector<int>>& cost) {
        if (idx == n) return 0;
        if (dp[idx][left][right] != -1) return dp[idx][left][right];

        long long ans = LONG_MAX;
        
        // try all combinations of colors for the current house
        for (int l = 1; l <= 3; l++) {
            for (int r = 1; r <= 3; r++) {
                // skip invalid color combinations
                if (l == r || l == left || r == right) continue;
                
                // compute the cost of painting the current house and move to the next
                ans = min(ans, cost[idx][l - 1] + cost[n - idx - 1][r - 1] + helper(l, r, idx + 1, n, cost));
            }
        }

        return dp[idx][left][right] = ans;
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        memset(dp, -1, sizeof(dp));
        return helper(0, 0, 0, n, cost);
    }
};
```
['C++']