Untitled

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        cuts=sorted(cuts)
        cuts.insert(0,0)
        cuts.append(n)
        N = len(cuts)
        dp = [[10**9 for i in range(N)] for j in range(N)]

        for p in range(N):
            j=p
            for i in range(N-p):

                if i==j or i+1==j:
                    dp[i][j] = 0
                
                for k in range(i+1,j):

                    dp[i][j] = min( dp[i][j] , dp[i][k] + dp[k][j] + cuts[j]-cuts[i] )
                
                j+=1
        
        return dp[0][-1]