Best Solution
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
```java []
class Solution {
    public long minCost(int n, int[][] cost) {
        long[][][] dp = new long[n/2][4][4];
        for(long[][] row1 : dp)
        for(long[] row2 : row1)
        Arrays.fill(row2,-1);
        return helper(0,cost,3,3,dp);
    }
    public long helper(int len,int[][] cost,int prev1,int prev2,long[][][] dp){
        int mid = cost.length/2;
        if(mid-len-1 < 0)
        return 0;
        if(dp[len][prev1][prev2] != -1)
        return dp[len][prev1][prev2];
        long curr = Long.MAX_VALUE;
            
        for(int i=0;i<3;i++){
                if(i != prev1)
                for(int j = 0;j<3;j++){
                    if(j != prev2  && i != j){
                        long curr2 = cost[mid-len-1][i] + cost[mid+len][j] + helper(len+1,cost,i,j,dp);
                        curr = Math.min(curr,curr2);
                    }
                }
            }
        return dp[len][prev1][prev2] = curr;
    }
}
```
['Java']