class Solution {
    public int minCost(int n, int[] cuts) {
        //Q-50 striver dp playlist , treat this as burst balloons

        //sort the array so that stick partitions doesn't overlap 
        Arrays.sort(cuts);

        //assume you have added 0 and length of the stick at 0th and end of the array
        len = n;
        return solve(cuts , 0 , cuts.length-1 , new Integer[cuts.length][cuts.length]);
    }

    /* calls as i have 7 length of stick and i have put a cut at here(i-->j) i will pass you 
    the current length give me minimum answer of the 2 partitions .
    */
    int len ;

    //Recursion -> exponentail Memo -> n*n*n |sc n*n + n*n
    public int solve(int[] cuts , int i , int j , Integer[][] dp){
        int n = cuts.length;
        if(i > j)return 0;

        if(dp[i][j] != null)
        return dp[i][j];

        int min = (int)1e9;
        for(int k  = i ; k <= j ; k++){
            //adding length of the stick 
            int temp = (j+1== n ? len : cuts[j+1]) - (i-1 == -1 ? 0 : cuts[i-1]);
            
            //calling for minimum partitions from the left and right stick
            temp += solve(cuts , i , k-1 , dp) + solve(cuts , k+1 , j , dp);

            min = Math.min(temp , min);
        }

        return dp[i][j] = min;
    }
}