2D DP | Bit Manipulation | DFS | 100% BEATS
IntuitionWe approach this problem using Dynamic Programming (DP), where each house can be painted in one of three colors. The challenge is to satisfy two constr
## Intuition
We approach this problem using **Dynamic Programming (DP)**, where each house can be painted in one of three colors. The challenge is to satisfy two constraints:
1. No two adjacent houses have the same color.
2. Equidistant houses from the ends must have different colors.

## Approach
### State Definition
We define `dp[idx][prev]` as the minimum cost to paint houses up to index `idx` with `prev` representing the colors of the last considered equidistant houses. Here, `prev` is a 4-bit integer:
- The leftmost 2 bits represent the color of the left house.
- The rightmost 2 bits represent the color of the right house.

### Bitmasking
We use **bitmasking** to store these previous colors compactly:
- `prev = (leftColor << 2) | rightColor`

### Transition
For each pair of equidistant houses, we iterate over all possible color combinations, ensuring they meet the given constraints.

### Recurrence Relation
The cost of painting the current pair is:

`dp[idx][prev] = min(cost[left][lc] + cost[right][rc] + dp[idx - 1][(lc << 2) | rc])`


### Base Case
When `idx < 0`, return `0` as there are no more houses to paint.

## Complexity
- **Time Complexity:** $$O(n)$$
- **Space Complexity:** $$O(n)$$

## Code
```cpp
class Solution
{
    int n;
    long long findMinCost(int idx, int prev, vector<vector<int>> &cost, vector<vector<long long>> &dp)
    {
        if (idx < 0)
            return 0;

        if (dp[idx][prev] != -1)
            return dp[idx][prev];

        int left = idx, right = n - idx - 1;
        int leftColor = prev >> 2, rightColor = prev & 3;

        long long minCost = LLONG_MAX;

        for (int lc = 0; lc < 3; lc++)
        {
            for (int rc = 0; rc < 3; rc++)
            {
                if (lc == rc || ((leftColor == lc || rightColor == rc) && idx != n / 2 - 1))
                    continue;

                long long costPair = static_cast<long long>(cost[left][lc]) + cost[right][rc];
                long long subProblem = findMinCost(idx - 1, (lc << 2) | rc, cost, dp);

                minCost = min(minCost, costPair + subProblem);
            }
        }

        return dp[idx][prev] = minCost;
    }

public:
    long long minCost(int n, vector<vector<int>> &cost)
    {
        this->n = n;
        vector<vector<long long>> dp(n / 2, vector<long long>(16, -1));

        return findMinCost(n / 2 - 1, 0, cost, dp);
    }
};
```
['Dynamic Programming', 'Greedy', 'Bit Manipulation', 'Depth-First Search', 'C++']