[Java] Simple Top-Down Approach
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 {

    Long cache[][][];

    public long minCost(int n, int[][] cost) {
        cache = new Long[n+1][4][4];
        return f(0, cost, 3, 3);
    }

    private long f(int i, int cost[][], int leftColor, int rightColor) {
        int n = cost.length;
        if(i > (n - 1 - i)) {
            return 0;
        }

        if(cache[i][leftColor][rightColor] != null) {
            return cache[i][leftColor][rightColor];
        }

        long ans = Long.MAX_VALUE;

        for(int j = 0;j < 3;j++) {
            if(j == leftColor) {
                continue;
            }
            for(int k=0;k<3;k++) {
                if(k == j || k == rightColor) {
                    continue;
                }
                ans = Math.min(ans, cost[i][j] + cost[n-1-i][k] + f(i+1, cost, j, k));
            }
        }

        return cache[i][leftColor][rightColor] = ans;
    }
}
```
['Java']