Top-Down 3D DP
IntuitionConstraints allow us to write O(n * 3 * 3) solution. Let's use this ability.ApproachMemoizing for current element's index, prev color and prev equidist
# Intuition
Constraints allow us to write `O(n * 3 * 3)` solution. Let's use this ability.

# Approach
Memoizing for current element's index, prev color and prev equidistant color. Then iterate over each color excluding non-allowed once to calculate the final minimal cost.

# Complexity
- Time complexity:
$$O(9 * n)$$

- Space complexity:
$$O(9 * n)$$

# Code
```java []
class Solution {
    public long minCost(int n, int[][] cost) {
        Long[][][] dp = new Long[n][3][3];
        long res = Long.MAX_VALUE;
        for (int c1 = 0; c1 < 3; c1++) {
            for (int c2 = 0; c2 < 3; c2++) {
                if (c2 == c1) {
                    continue;
                }
                res = Math.min(res, count(dp, cost, 1, c1, c2) + cost[0][c1] + cost[cost.length - 1][c2]);
            }
        }
        return res;
    }

    static long count(Long[][][] dp, int[][] cost, int i, int color1, int color2) {
        if (i == cost.length / 2) {
            return 0;
        }
        if (dp[i][color1][color2] != null) {
            return dp[i][color1][color2];
        }
        long res = Long.MAX_VALUE;
        for (int c1 = 0; c1 < 3; c1++) {
            if (c1 == color1) {
                continue;
            }
            for (int c2 = 0; c2 < 3; c2++) {
                if (c2 == c1 || c2 == color2) {
                    continue;
                }
                res = Math.min(res, count(dp, cost, i + 1, c1, c2) + cost[i][c1] + cost[cost.length - 1 - i][c2]);
            }
        }
        return dp[i][color1][color2] = res;
    }
}
```
['Dynamic Programming', 'Memoization', 'Java']