⭐️Simple DP solution ✅  with explanation || Recursive DP || Beats 100% || C++ | Java | python
Please Upvote if you find any help from this.IntuitionIt is a DP problem and given the constraints of 1e5, we need a solution of time complexity of linear or lo

Please Upvote if you find any help from this.
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
It is a DP problem and given the constraints of 1e5, we need a solution of time complexity of linear or logarithmic time of it or smaller then both.

# Approach
<!-- Describe your approach to solving the problem. -->
As the colour of houses equidistant from the end points cannot be same we need to maintain the state of the house $$i$$ while coloring the house $$n-i-1$$.

So doing this will require much more memory space and time. So we just traverse from $$i=0 $$to $$i=(n/2-1)$$. And while coloring the house $$i$$, we will also color the house $$n-i-1$$(the one equidistant from end point corresponding to $$i$$th house). 

So for coloring the 2 houses at a time we need 2 colors which represent the color of adjacent i.e $$i-1$$th house for $$i$$th house and $$n-i$$th house for $$(n-i-1)$$th house.

Also there are only 3 possible colors, so total possible pairs of coloring 2 houses will be $$3*3=9$$. But at max only $$6$$ valid pairs will be there.So we can memoize the colors also.

##### **So we need 3 states of DP:**
1. The current house number.
2. The left color of the $$i$$th house (which is adjacent to it). 
3. The right color of the $$n-i-1$$th house (which is adjacent to it). 

While coloring we select valid pairs only to avoid same adjacent coloring and same coloring for equidistant from end houses.

### This is the dp part:
```cpp []
vector<vector<vector<ll>>> dp;

    long long sol(vector<vector<int>>& c, int l, int r, int i) 
    {
        int n = c.size();
        if (i >= n / 2) 
            return 0;

        if (dp[i][l][r] != (-1)) 
            return dp[i][l][r];

        vector<int> lftc, rgtc;
        for (int j = 0; j < 3; j++) 
        {
            if (l != j) 
                lftc.push_back(j);
            if (r != j) 
                rgtc.push_back(j);
        }
        ll ans = 1e14;
        for (int h : lftc) 
        {
            for (int j : rgtc) 
            {
                if (h == j) 
                    continue;
                ll cl = c[i][h], cr = c[n - i - 1][j];
                ans = min(ans, cl + cr + sol(c, h, j, i + 1));
            }
        }
        return dp[i][l][r] = ans;
    }
```

# Complexity
- Time complexity:**$$O(9n)$$**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
We traverse only once for each house so O(9*n)=(n).

 (*9 is because we will make at most 9 pairs of coloring. From this 9 pairs at most 6 pairs will only be possible).

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

# Code
```cpp []
#define ll long long
class Solution {
public:
    vector<vector<vector<ll>>> dp;

    long long sol(vector<vector<int>>& c, int l, int r, int i) 
    {
        int n = c.size();
        if (i >= n / 2) 
            return 0;

        if (dp[i][l][r] != (-1)) 
            return dp[i][l][r];

        vector<int> lftc, rgtc;
        for (int j = 0; j < 3; j++) 
        {
            if (l != j) 
                lftc.push_back(j);
            if (r != j) 
                rgtc.push_back(j);
        }
        ll ans = 1e14;
        for (int h : lftc) 
        {
            for (int j : rgtc) 
            {
                if (h == j) 
                    continue;
                ll cl = c[i][h], cr = c[n - i - 1][j];
                ans = min(ans, cl + cr + sol(c, h, j, i + 1));
            }
        }
        return dp[i][l][r] = ans;
    }

    long long minCost(int n, vector<vector<int>>& c) {
        dp.resize(n / 2 + 1, vector<vector<ll>>(4, vector<ll>(4, -1)));
        return sol(c, 3, 3, 0);
    }
};
```
```Java []
class Solution {
    public long minCost(int n, int[][] cost) 
    {
        long[][][] dp = new long[n / 2 + 1][4][4];
        for (long[][] layer : dp) {
            for (long[] row : layer) {
                Arrays.fill(row, -1);
            }
        }
        return solve(cost, 3, 3, 0, dp);
    }
    private long solve(int[][] cost, int l, int r, int i, long[][][] dp) {
        int n = cost.length;
        if (i >= n / 2) {
            return 0;
        }
        if (dp[i][l][r] != -1) {
            return dp[i][l][r];
        }
        List<Integer> leftChoices = new ArrayList<>();
        List<Integer> rightChoices = new ArrayList<>();
        for (int j = 0; j < 3; j++) {
            if (l != j) {
                leftChoices.add(j);
            }
            if (r != j) {
                rightChoices.add(j);
            }
        }
        long ans = Long.MAX_VALUE;
        for (int h : leftChoices) {
            for (int j : rightChoices) {
                if (h == j) {
                    continue;
                }
                long cl = cost[i][h];
                long cr = cost[n - i - 1][j];
                ans = Math.min(ans, cl + cr + solve(cost, h, j, i + 1, dp));
            }
        }
        return dp[i][l][r] = ans;
    }
}

```
``` Python []
class Solution:
    def __init__(self):
        self.dp = None

    def solve(self, c, l, r, i):
        n = len(c)
        if i >= n // 2:
            return 0

        if self.dp[i][l][r] != -1:
            return self.dp[i][l][r]

        left_choices = [j for j in range(3) if j != l]
        right_choices = [j for j in range(3) if j != r]

        ans = float('inf')

        for h in left_choices:
            for j in right_choices:
                if h == j:
                    continue
                cl = c[i][h]
                cr = c[n - i - 1][j]
                ans = min(ans, cl + cr + self.solve(c, h, j, i + 1))

        self.dp[i][l][r] = ans
        return ans

    def minCost(self, n, c):
        self.dp = [[[-1] * 4 for _ in range(4)] for _ in range(n // 2 + 1)]
        return self.solve(c, 3, 3, 0)

```



['Array', 'Dynamic Programming', 'Recursion', 'C++', 'Java', 'Python3']