Simple 3D DP ✅ | C++ | Beginner friendly
CodeComplexity
Time complexity: O(N)

Space complexity: O(100000*16)

# Code
```cpp []
#define ll long long int
class Solution {
public:
    ll dp[100000][4][4];
    ll solve(int idx, int prev_color1, int prev_color2, int n, vector<vector<int>>& cost){
        if(idx == n) return 0;
        if(dp[idx][prev_color1][prev_color2] != -1) return dp[idx][prev_color1][prev_color2];
        ll ans= 1e15;
        for(int new_color1 = 1; new_color1 < 4; new_color1++){
            for(int new_color2 = 1; new_color2 < 4; new_color2++){
                if(new_color1 == new_color2 || new_color1 == prev_color1 || new_color2 == prev_color2) continue;
                ans = min(ans, solve(idx + 1, new_color1, new_color2, n, cost) + cost[idx][new_color1 - 1]+ cost[2*n - 1 - idx][new_color2 - 1]);
            }
        }
        return dp[idx][prev_color1][prev_color2]=ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        n = n/2;
        memset(dp, -1, sizeof(dp));
        return solve(0, 0, 0, n, cost);     
    }
};
```

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

- Space complexity: O(100000*16)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Dynamic Programming', 'C++']