Recursive DP Solution with Naïve Approach
IntuitionThe Intuition here is to make sure entire cost for the painting of the houses is minimum by adhering to the conditions mentioned, the naive way of thin
# Intuition
The Intuition here is to make sure entire cost for the painting of the houses is minimum by adhering to the conditions mentioned, the naive way of thinking is to select a paint for **$$i$$**<sup>th</sup> house and eventually select the paint for the **$$i+1$$**<sup>th</sup> house with different color also making sure the **$$n-i-1$$**<sup>th</sup> house also has a different color.
In my naive logic, I kept a $$prev$$ flag to track the previous houses(**$$i-1$$**<sup>th</sup>) chosen colour and also a vector to capture the **$$n-i-1$$**<sup>th</sup> color.

# Naive Solution (Recursive without DP)
```
class Solution {
public:
    long long findAns(vector<vector<int>>& cost, int i, int n, int prev, vector<int> v){
        if(i >= n) return 0;
        int ans = INT_MAX;
        for(int j=0;j<3;j++){
            if(j != prev && j != v[n-i-1]){
                v[i] = j;
                int val = cost[i][j] + findAns(cost, i+1, n, j, v);
                ans = min(ans, val);
            }
        }
        return ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<int> v(n, -1);
        return findAns(cost, 0, n, -1, v);
    }
};
```
The above solution works perfectly fine and traverses all the way till end, also the loop is because every house is given with a choice of 3 selections and we capture the paint for the **$$n-i-1$$**<sup>th</sup> house. But this hits a TLE and also here we have only 2 variables and a map so difficult to put it in a DP. Hence the next solution.

# Approach
<!-- Describe your approach to solving the problem. -->
The approach here is to basically keep track of the $$prev$$ and complementary(**$$n-i-1$$**<sup>th</sup>) $$comp$$ house and recurse only till $$n/2$$ but also if a paint is chosen for the **$$i$$**<sup>th</sup> house then we need to quickly assign a paint to the **$$n-i-1$$**<sup>th</sup> house adhering to the conditions provided in the Question.

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

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

# Code
```cpp []
class Solution {
public:
    vector<vector<vector<long long>>> dp;
    long long findAns(vector<vector<int>>& cost, int i, int n, int prev, int comp){
        if(i >= n/2) return 0;
        if(dp[i][prev+1][comp+1] != -1) return dp[i][prev+1][comp+1];
        long long ans = LONG_MAX;
        for(int j=0;j<3;j++){
            if(j != prev){
                for(int k=0;k<3;k++){
                    if(j != k && k != comp){
                        long long val = cost[i][j] + cost[n-i-1][k] + findAns(cost, i+1, n, j, k);
                        ans = min(ans, val);
                    }
                }
            }
        }
        return dp[i][prev+1][comp+1] = ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<int> v(n, -1);
        dp.resize(n+1, vector<vector<long long>>(4, vector<long long>(4, -1)));
        return findAns(cost, 0, n, -1, -1);
    }
};
```
['Dynamic Programming', 'Recursion', 'C++']