C++ DP (house, lastLeftColor, lastRightColor): Tabulation and Memoization
*Tabulation AC submissionComplexity

Time complexity: O(n)


Space complexity: O(n)

Code (Memoization)Code (Tabulation)
![image.png](https://assets.leetcode.com/users/images/9722605c-b6d9-4272-bbc2-544f0521b4e9_1737260347.0368838.png)
*Tabulation AC submission
# Complexity
- Time complexity: $O(n)$

- Space complexity: $O(n)$

---
# Code (Memoization)
```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
  		int mid = n/2;
  		vector memo(mid, vector(3, vector(3, -1LL)));
  		auto go = [&](this auto&& go, int i, int leftColor, int rightColor) -> long long {
  			if(i >= mid) return 0LL;	
  			if(leftColor >= 0LL && memo[i][leftColor][rightColor] >= 0LL) return memo[i][leftColor][rightColor];

  			long long ans = LLONG_MAX;
  			for(int nextLeft = 0; nextLeft < 3; nextLeft++) {
  				if(leftColor == nextLeft) continue;
  				for(int nextRight = 0; nextRight < 3; nextRight++) {
  					if(rightColor == nextRight || nextLeft == nextRight) continue;
  					ans = min(ans, (long long) cost[i][nextLeft] + cost[n-i-1][nextRight] + go(i + 1, nextLeft, nextRight));
  				}
  			}
  			if(leftColor >= 0) memo[i][leftColor][rightColor] = ans;
  			return ans;
  		};
  		return go(0, -1, -1);
    }
};
```
---
# Code (Tabulation)
```cpp []
#include <bits/stdc++.h>
using namespace std;

long long dp[50001][3][3];
class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
  		int mid = n/2;
        long long ans = LLONG_MAX;
        // base case
        for(int a = 0; a < 3; a++) for(int b = 0; b < 3; b++) dp[mid][a][b] = 0LL;
        for(int i = mid - 1; i >= 0; i--) {
            for(int leftColor = 0; leftColor < 3; leftColor++) {
                for(int rightColor = 0; rightColor < 3; rightColor++) {
                    if(leftColor == rightColor) continue;
                    dp[i][leftColor][rightColor] = LLONG_MAX;

                    for(int nextLeft = 0; nextLeft < 3; nextLeft++) {
                        if(leftColor == nextLeft) continue;
                        for(int nextRight = 0; nextRight < 3; nextRight++) {
                            if(rightColor == nextRight || nextLeft == nextRight) continue;
                            dp[i][leftColor][rightColor] = min(dp[i][leftColor][rightColor], 
                                (long long) cost[i][nextLeft] + cost[n-i-1][nextRight] + dp[i + 1][nextLeft][nextRight]);
                        }
                    }
                    
                    if(i == 0) ans = min(ans, dp[i][leftColor][rightColor]);
                }
            }
        }
  		return ans;
    }
};
```
['C++']