Memoized DP Solution
Minimum Cost to Paint HousesProblem DescriptionYou are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cos
# Minimum Cost to Paint Houses

## Problem Description

You are given an even integer `n` representing the number of houses arranged in a straight line, and a 2D array `cost` of size `n x 3`, where `cost[i][j]` represents the cost of painting house `i` with color `j + 1`.

The houses will look beautiful if they satisfy the following conditions:

1. No two adjacent houses are painted the same color.
2. Houses equidistant from the ends of the row are not painted the same color. For example, if `n = 6`, houses at positions (0, 5), (1, 4), and (2, 3) are considered equidistant.

Return the minimum cost to paint the houses such that they look beautiful.

## Approach

1. **Dynamic Programming (DP)**: 
   We use a DP-based approach to store the minimum cost of painting up to a certain house index with specific constraints.

2. **State Representation**:
   - `dp[in][p1][p2]`: The minimum cost to paint the first `in` pairs of houses, where `p1` is the color of the previous house on the left, and `p2` is the color of the previous house on the right.

3. **Recursive Function**:
   - For each house pair, we try all valid combinations of colors for the current house (`c1`) and the equidistant house (`c2`).
   - The recursive function returns the minimum cost of painting the houses while satisfying the constraints:
     - Adjacent houses must have different colors.
     - Equidistant houses must have different colors.

4. **Base Case**: 
   - When all pairs of houses are painted (`in >= n/2`), return `0`.

5. **Memoization**: 
   - Memoization is used to avoid recomputing overlapping subproblems.

## Time and Space Complexity

- **Time Complexity**: 
  - The time complexity is `O(n)` as for each house pair, we iterate over the possible color choices for both houses.

- **Space Complexity**: 
  - The space complexity is `O(n)` due to the size of the DP table.

## Code

```cpp
#define ll long long
class Solution {
public:
    ll helper(int in, int p1, int p2, vector<vector<int>>& cost, vector<vector<vector<ll>>>& dp, int n) {
        // Base case: All houses are painted
        if (in >= n / 2) return 0;

        // Check if the result is already computed
        if (dp[in][p1][p2] != -1) return dp[in][p1][p2];

        ll ans = 1E15; // Initialize to a large value

        // Iterate over all valid color combinations
        for (int c1 = 0; c1 < 3; c1++) {
            if (c1 != p1) { // Ensure no two adjacent houses have the same color
                for (int c2 = 0; c2 < 3; c2++) {
                    if (c2 != p2 && c2 != c1) { // Ensure equidistant houses have different colors
                        // Compute the cost for this configuration
                        ll res = cost[in][c1] + cost[n - in - 1][c2] + helper(in + 1, c1, c2, cost, dp, n);
                        ans = min(ans, res); // Update the minimum cost
                    }
                }
            }
        }

        // Store and return the result
        return dp[in][p1][p2] = ans;
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        // Initialize the DP table with -1
        vector<vector<vector<ll>>> dp(n / 2, vector<vector<ll>>(4, vector<ll>(4, -1)));

        // Start with no previous colors assigned
        return helper(0, 3, 3, cost, dp, n);
    }
};

['Dynamic Programming', 'Greedy', 'Memoization', 'C++']