Much cleaner code | Recursive DP | C++
IntuitionThe problem might seem tricky initially because it involves satisfying two distinct constraints: no two adjacent houses can have the same color, and eq
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem might seem tricky initially because it involves satisfying two distinct constraints: no two adjacent houses can have the same color, and equidistant houses from the ends of the row must also have different colors. The key insight is to tackle these constraints by coloring pairs of equidistant houses together, starting from the outermost pair and moving inward.

I had solved this problem before for Snowflake OA and hence I knew the trick. The trick here is to color both the equidistant pair together. 

# Approach
<!-- Describe your approach to solving the problem. -->
To solve the problem, we use two pointers: left and right. The left pointer starts from the beginning of the row, and the right pointer starts from the end, denoting the pair of equidistant houses being colored. For each pair, we iterate over all possible colors for the left house and the right house while ensuring:

The left house's color is different from the previous adjacent house's color.
The right house's color is different from the next adjacent house's color.
The left and right houses in the current pair are not painted the same color.
I use a recursive approach with memoization to minimize the total cost, leveraging the overlap in subproblems. This way, the solution efficiently handles the constraints while ensuring the minimum cost.

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

# Code
```cpp []
class Solution {
public:
    vector<vector<vector<long long>>> dp;
    long long helper(int left, int right, vector<vector<int>> &cost, int prevColorLeft, int nextColorRight) {
        if(left > right) {
            return 0;
        }
        if(dp[left][prevColorLeft][nextColorRight] != -1) {
            return dp[left][prevColorLeft][nextColorRight];
        }
        long long ans = 1e18;
        for(int colorL=0;colorL<3;colorL++) {
            if(colorL != prevColorLeft) {
                for(int colorR = 0;colorR<3;colorR++) {
                    if(colorR != nextColorRight && colorR != colorL) {
                        ans = min(ans, cost[left][colorL] + cost[right][colorR] + helper(left + 1, right - 1, cost, colorL, colorR));
                    }
                }
            }
        }
        return dp[left][prevColorLeft][nextColorRight] = ans;
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        this->dp.resize(n, vector<vector<long long>>(4, vector<long long>(4, -1)));
        return helper(0, n-1, cost, 3, 3);
    }
};
```
['C++']