Tabulation Solution 
IntuitionJust write the memoization approach first and then convert it tabulation.Approachdp[i][j][k] = cost of paiting first and last (i + 1) houses where the
# Intuition
Just write the memoization approach first and then convert it tabulation.

# Approach
dp[i][j][k] = cost of paiting first and last (i + 1) houses where the color of (i + 1)th house is j and color of (n - i - 1)th house is k. Forget about the middle houses. 

So dp[0][2][1] = color of painting the first and last house in color 2 and 1 respectively. 

Now when moving on to filling the dp[i + 1][j][k] state, use the dp[i - 1][x][y] state where j != x && k != y && x != y && j != k.

# Complexity
- Time complexity:
Linear

- Space complexity:
Linear

# Code
```cpp []
class Solution {
public:
    long long dp[100005][4][4];
    long long minCost(int n, vector<vector<int>>& cost) {
        // The cost of painting just considering the first and last house
        for(int i = 0; i <= 2; i++){
            for(int j = 0; j <= 2; j++){
                if(i != j){
                    dp[0][i][j] = cost[0][i] + cost[n - 1][j];
                 }
            }
        } 
        // The cost of painting the first and last (i + 1) houses combined
        for(int i = 1; i <= n - i - 1; i++){
            // this is to handle the middle house (total houses are odd)
            if(i == n - i - 1){
                long long ans = LLONG_MAX;
                for(int j = 0; j <= 2; j++){
                    for(int k = 0; k <= 2; k++){
                        for(int l = 0; l <= 2; l++){
                            if(j != k && j != l && k != l){
                                ans = min(ans, cost[i][j] + dp[i - 1][k][l]);
                            }
                            
                        }
                    }
                }
                return ans;
            }
            /*
            j = color of ith house
            x = color of i - 1th house
            so j != x
            k = color of (n - i - 1)th house
            y = color of (n - i) th house

            hourse order .... x,j........k,y......
            so x != y && j != k && x != j && k != y
            */
            for(int j = 0; j <= 2; j++){
                for(int k = 0; k <= 2; k++){
                    long long ans = LLONG_MAX;
                    if(j != k){
                        for(int x = 0; x <= 2; x++){
                            for(int y = 0; y <= 2; y++){
                                if(x != y && j != x && k != y){
                                    ans = min(ans, cost[i][j] + cost[n - i - 1][k] + dp[i-1][x][y]);
                                }
                            }
                        }
                    }
                    dp[i][j][k] = ans;
                }
            }
        }
        long long ans = LLONG_MAX;
        for(int i = 0; i <= 2; i++){
            for(int j = 0; j <= 2; j++){
                if(i != j){
                    ans = min(ans, dp[n/2 - 1][i][j]);
                }
            }
        }
        return ans;
    }
};
```
['C++']