DFS with  memoization
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
```csharp []
public class Solution {

    public long MinCost(int n, int[][] cost) {
        int[][] combi = new int[][]
    {
        new int[] {0, 1},
        new int[] {0, 2},
        new int[] {1, 0},
        new int[] {2, 0},
        new int[] {1, 2},
        new int[] {2, 1}
    };
    int t=cost.Length/2;
    long[][][] dp= new long[t][][];
    for(int i=0;i<t;i++)
    {
        dp[i] = new long[4][];
        for(int j=0;j<4;j++)
        {
            dp[i][j]= new long[4];
            for(int k=0;k<4;k++)
            {
                dp[i][j][k]=-1;
            }
        }
    }

        return Dfs(0,cost,3,3,combi,dp);
    }

    private long Dfs(int index, int[][] cost,int prev1,int prev2,int[][] combi,long[][][] dp)
    {
        int n=cost.Length;
        if(index>=n/2)
        {
            return 0;
        }
        long total=long.MaxValue;
        if(dp[index][prev1][prev2]!=-1)
        {
            return dp[index][prev1][prev2];
        }
        for(int i=0;i<6;i++)
        {
            int c1=combi[i][0];
            int c2=combi[i][1];
            if(c1!=prev1&&c2!=prev2)
            {
                long ct=Dfs(index+1,cost, c1,c2,combi,dp);
                total=Math.Min(total, cost[index][c1]+cost[n-1-index][c2]+ct);
            }
        }
        dp[index][prev1][prev2]=total;
        
        return total;

    }
}
```
['C#']