fold the array.. memoisation
Intuitionhandle the array from both ends.. to do this we can use dp and access both respective indices in each callApproachComplexity

Time complexity: O(n)


S
# Intuition
handle the array from both ends.. to do this we can use dp and access both respective indices in each call

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

# Complexity
- Time complexity: O(n)

- Space complexity: O(n)

# Code
```cpp []
#define ll long long

class Solution {
public:
    ll dp[100010][4][4];
    ll bruteforce(int p1, int p2, int cur, int n, vector<vector<int>>& cost) {
        if(cur == n / 2)
            return 0;

        if(dp[cur][p1][p2] == -1){
            ll i1 = cur, i2 = n - cur - 1, ans = LLONG_MAX;
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    if(i != p1 && j != p2 && i != j){
                        ans = min(ans, 1ll * cost[i1][i] + cost[i2][j] + bruteforce(i, j, cur + 1, n, cost));
                    }
                }
            }

            dp[cur][p1][p2] = ans;
        }

        return dp[cur][p1][p2];
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= 3; j++)
                for(int k = 0; k <= 3; k++)
                    dp[i][j][k] = -1;
        return bruteforce(3, 3, 0, n, cost);
    }
};
```
['C++']