Leetcode 1547

class Solution {
    Integer[][] memo;
    int newCuts[];
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        memo = new Integer[m + 2][m + 2];
        newCuts = new int[m + 2];
        System.arraycopy(cuts, 0, newCuts, 1, m);
        newCuts[m + 1] = n;
        Arrays.sort(newCuts);
        return dp(0,newCuts.length - 1);
    }
    private int dp(int left, int right){
        // base case 
        if(right - left == 1) return 0;

        if(memo[left][right] != null) return memo[left][right];

        int res = Integer.MAX_VALUE;
        for(int pivot = left + 1; pivot < right; pivot ++){
            int cost = dp(left,pivot) + dp(pivot,right) + newCuts[right] - newCuts[left];
            res = Math.min(res,cost);
        }
        memo[left][right] = res;
        return res;
    }
}