Untitled

class Solution {
    private int[][] t = new int[103][103];
    
    private int solve(int[] cuts, int left, int right) {
        if (right - left == 1)
            return 0;
        
        if (t[left][right] != -1)
            return t[left][right];
        
        int result = Integer.MAX_VALUE;
        
        for (int index = left + 1; index <= right - 1; index++) {
            int cost = solve(cuts, left, index) + solve(cuts, index, right) + (cuts[right] - cuts[left]);
            result = Math.min(result, cost);
        }
        
        return t[left][right] = result;
    }
    
    public int minCost(int n, int[] cuts) {
        // Sort the cuts array
        Arrays.sort(cuts);
        
        // Create a new array with 0 at beginning and n at end
        int[] newCuts = new int[cuts.length + 2];
        newCuts[0] = 0;
        System.arraycopy(cuts, 0, newCuts, 1, cuts.length);
        newCuts[newCuts.length - 1] = n;
        
        // Initialize memoization table with -1
        for (int[] row : t) {
            Arrays.fill(row, -1);
        }
        
        return solve(newCuts, 0, newCuts.length - 1);
    }
}