Recursion 
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
class Solution {
public:
    
    long long int min(long long int a, long long int b) {
        return (a < b) ? a : b;
    }

    
    long long rec(int idx, int n, int flag, int tail, vector<vector<int>>& cost, vector<vector<vector<long long>>>& dp) {
        if (n - idx - 1 <= idx) { 
            return 0;
        }

        if (dp[idx][flag][tail] != -1) {
            return dp[idx][flag][tail];
        }

        long long ans = LLONG_MAX; 

        
        if (idx == 0 && tail == 0) {
            ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 1, cost, dp) + cost[n - idx - 1][1]);
            ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 2, cost, dp) + cost[n - idx - 1][2]);
            ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 0, cost, dp) + cost[n - idx - 1][0]);
            ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 2, cost, dp) + cost[n - idx - 1][2]);
            ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 1, cost, dp) + cost[n - idx - 1][1]);
            ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 0, cost, dp) + cost[n - idx - 1][0]);
        }

        // For subsequent houses
        if (idx >= 1) {
            if (flag == 0 && tail == 1) {
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 0, cost, dp) + cost[n - idx - 1][0]);
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 2, cost, dp) + cost[n - idx - 1][2]);
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 0, cost, dp) + cost[n - idx - 1][0]);
            } else if (flag == 0 && tail == 2) {
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 0, cost, dp) + cost[n - idx - 1][0]);
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 0, cost, dp) + cost[n - idx - 1][0]);
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 1, cost, dp) + cost[n - idx - 1][1]);
            } else if (flag == 1 && tail == 0) {
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 1, cost, dp) + cost[n - idx - 1][1]);
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 2, cost, dp) + cost[n - idx - 1][2]);
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 1, cost, dp) + cost[n - idx - 1][1]);
            } else if (flag == 1 && tail == 2) {
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 0, cost, dp) + cost[n - idx - 1][0]);
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 1, cost, dp) + cost[n - idx - 1][1]);
                ans = min(ans, cost[idx][2] + rec(idx + 1, n, 2, 1, cost, dp) + cost[n - idx - 1][1]);
            } else if (flag == 2 && tail == 1) {
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 0, cost, dp) + cost[n - idx - 1][0]);
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 2, cost, dp) + cost[n - idx - 1][2]);
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 2, cost, dp) + cost[n - idx - 1][2]);
            } else if (flag == 2 && tail == 0) {
                ans = min(ans, cost[idx][1] + rec(idx + 1, n, 1, 2, cost, dp) + cost[n - idx - 1][2]);
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 1, cost, dp) + cost[n - idx - 1][1]);
                ans = min(ans, cost[idx][0] + rec(idx + 1, n, 0, 2, cost, dp) + cost[n - idx - 1][2]);
            }
        }

        return dp[idx][flag][tail] = ans;
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        
        vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(3, vector<long long>(3, -1)));
        return rec(0, n, 0, 0, cost, dp);
    }
};

```
['C++']