Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
 
Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

 
Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

Difficulty: interview

Starter code:

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        

Solutions:
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.sort()
        from functools import lru_cache
        @lru_cache(None)
        def helper(i = 0, j = n):
            ans = math.inf
            for c in cuts:
                if c <= i: continue
                if c >= j: break
                ans = min(ans, j - i + helper(i, c) + helper(c, j))
            if ans == math.inf:
                return 0
            return ans
        return helper()

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def cut(left, right):
            # if not subcuts:
            #     return 0
            # elif (left, right) in dp:
            #     return dp[(left, right)]
            
            res = right - left
            min_subproblem = float('inf')
            for c in cuts:
                if left < c < right:
                    min_subproblem = min ( min_subproblem, cut(left, c) + cut(c, right))
            
            if min_subproblem == float('inf'):
                return 0
            
            res += min_subproblem
            # dp[(left, right)] = res
            return res
        
        # dp = {}
        
        return cut(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def min_cost(left_end=0, right_end=n):
            if any(left_end < cut < right_end for cut in cuts):
                cost = right_end - left_end
                nxt_costs = min(
                    min_cost(left_end, cut) + min_cost(cut, right_end)
                    for cut in cuts
                    if left_end < cut < right_end
                )
                return nxt_costs + cost
            return 0
        
        return min_cost()

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def dp(l, r):
            if any(l < c < r for c in cuts):
                ans = r - l + min([dp(l, c) + dp(c, r) for c in cuts if l < c < r], default=0)
                return ans
            return 0
        return dp(0, n)


        
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        @lru_cache(None)
        def min_cost(left_end=0, right_end=n):
            if any(left_end < cut < right_end for cut in cuts):
                cost = right_end - left_end
                nxt_costs = min(
                    min_cost(left_end, cut) + min_cost(cut, right_end)
                    for cut in cuts
                    if left_end < cut < right_end
                )
                return nxt_costs + cost
            return 0
        
        return min_cost()

from functools import lru_cache
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.sort()
        
        @lru_cache(maxsize=None)
        def dfs(l, r):
            m = 0xffffffff
            for c in cuts:
                if l < c < r:
                    m = min(m, dfs(l, c) + dfs(c, r))
            return 0 if m == 0xffffffff else m + r - l

        return dfs(0, n)

from functools import lru_cache
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        
        
        lim = len(cuts)
        
        
        @lru_cache(None)
        def r(i,j):
            
           
            tmp = []
            for k in cuts:
                if k>i and k<j:
                    tmp.append((j-i)+r(i,k)+r(k,j))
            if tmp==[]:return 0        
              
            return min(tmp)
            
            
        return r(0,n)

from itertools import permutations
from functools import lru_cache
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def bin_search(t,d):
            if t > cuts[-1]:
                return float('inf') if d == '+' else len(cuts)-1
            if t < cuts[0]:
                return float('-inf') if d == '-' else 0
            
            l,r=0,len(cuts)-1
            while l <= r:
                m = (l+r)//2
                if cuts[m] > t:
                    r = m - 1
                elif cuts[m] < t:
                    l = m + 1
                else:
                    return m+1 if d == '+' else m-1
            return l if d == '+' else r
        
        @lru_cache(None)
        def helper(st,end):
            # curr_cuts = [c for c in cuts if st < c < end]
            l = bin_search(st,'+')
            r = bin_search(end,'-')
            # print(st,end,[cuts[i] for i in range(l,r+1)])
            n = max(r - l + 1,0)
            if n == 1:
                return end-st
            if n == 0:
                return 0
            
            min_cost = float('inf')
            for i in range(l,r+1):     
                min_cost = min(min_cost,end-st + helper(st,cuts[i]) + helper(cuts[i],end))
    
            return min_cost
    
        cuts.sort()
        return helper(0,n)



from itertools import permutations
from functools import lru_cache
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def helper(st,end):
            curr_cuts = [c for c in cuts if st < c < end]
            n = len(curr_cuts)
            if n == 1:
                return end-st
            if n == 0:
                return 0
            
            min_cost = float('inf')
            for cut in curr_cuts:     
                min_cost = min(min_cost,end-st + helper(st,cut) + helper(cut,end))
    
            return min_cost
    
        cuts.sort()
        return helper(0,n)



from functools import lru_cache

class Solution:

    def minCost(self, n: int, cuts: List[int]) -> int:
        @lru_cache(None)
        def minCost_r(k,l):
            if l-k <= 1: return 0
            mc = float('inf')
            for c in cuts:
                if c <= k or c >= l: continue
                mc = min(mc, minCost_r(k,c) + minCost_r(c,l) + (l-k))
            return mc if mc != float('inf') else 0
            
        return minCost_r(0,n)


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def solve(l, r):
            best = n * n
            found = False
            for c in cuts:
                if c <= l or c >= r:
                    continue
                found = True
                best = min(best, r - l + solve(l, c) + solve(c, r))
            
            if not found:
                return 0
            return best
        
        return solve(0, n)

import functools

class Solution:

  @functools.lru_cache(None)
  def dp(self, i, j):
    # print(f\"{i}..{j}\")
    if j - i < 2:
      # print(f\"{i}..{j} -> {0}\")
      return 0
    options = [j - i + self.dp(i,k) + self.dp(k,j) for k in self.cuts if i < k and k < j]
    if len(options) == 0:
      # print(f\"{i}..{j} -> {0}\")
      return 0
    result = min(options)
    # print(f\"{i}..{j} -> {result}\")
    return result

  def minCost(self, n: int, cuts) -> int:
    self.cuts = cuts
    return self.dp(0, n)


from typing import List
import functools

class Solution(object):
    def minCost(self, n, cuts):
        @functools.lru_cache(None)
        def get_cuts(l,r):
            return [c for c in cuts if c>l and c<r] 

        @functools.lru_cache(None)
        def solve(l, r):
            mycuts= get_cuts(l,r)
            if len(mycuts) == 1 : return r-l 
            if len(mycuts) == 0 : return 0

            minn = 1e9
            for pos in mycuts:
                left_cost = solve(l, pos)
                right_cost = solve(pos, r)
                minn = min(minn, left_cost+right_cost + r-l ) 
            return minn

        cuts = sorted(cuts)
        return solve(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp={}
        position={}
        cuts.sort()
        for i in range(len(cuts)):
            position[cuts[i ]]=i
        def f(s,e):
            if (s,e) in dp:
                return dp[(s,e)]
            else:
                res=float('inf')
                i=0
                if s<cuts[0]:
                    i=0
                else:
                    i=position[s]+1
                
                # while i<len(cuts) and cuts[i]<=s:
                #     i+=1
                # print(\"i\"+str(i))
                j=len(cuts)-1
                if e>cuts[len(cuts)-1]:
                    j=len(cuts)-1
                else:
                    j=position[e]-1
                # while cuts[j]>=e and j>=0:
                #     j-=1
                # print(j)
                if i>j:
                    dp[(s,e)]=0
                    return 0
                for k in range(i,j+1):
                    # dp[(s,e)]=dp[(s,cuts[k])]+dp[(cuts[k],e )]  +s-e
                    res=min(res,f(s,cuts[k])+f(cuts[k],e)+e-s)
                dp[(s,e)]=res
                return dp[(s,e)]

        return f(0,n)

from collections import defaultdict

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]

        cache = defaultdict(int)
        return dfs(0, n)


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cache = dict()
        def recurse(start, end):
            key = (start, end)
            if key in cache: 
                return cache[key]
            if start >= end:
                return 0
            minCost = float('inf')
            len = end - start
            for cut in cuts:
                if cut > start and cut < end:
                    first = recurse(start, cut)
                    second = recurse(cut, end)
                    minCost = min(minCost, len + first + second)
            
            if minCost == float('inf'):
                minCost = 0
            cache[key] = minCost
            return minCost
        cuts.sort()
        ans = recurse(0, n)
        return ans
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        if cuts==None or len(cuts)==0:
            return 0
        
        dp = defaultdict(int)
        def dfs(start, end):
            if (start, end) in dp:
                return dp[(start, end)]
            
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                dp[(start, end)] = 0
            else:
                dp[(start, end)] = end - start + min_val
            return dp[(start, end)]

        return dfs(0, n)     
        

                    
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        min_costs = {}
        cut_set = set(cuts)
        def find_min_cost(start: int, end: int):
            if (start, end) in min_costs:
                return min_costs[(start, end)]
            cuts_in = []
            for i in cut_set:
                if i > start and i < end:
                    cuts_in.append(i)
            if len(cuts_in) == 0:
                min_costs[(start, end)] = 0
                return 0
            if len(cuts_in) == 1:
                min_costs[(start, end)] = end - start
                return end - start
            result = len(cuts_in) * (end - start)
            for cut in cuts_in:
                subresult = end - start
                subresult += find_min_cost(start, cut)
                subresult += find_min_cost(cut, end)
                if subresult < result:
                    result = subresult
            min_costs[(start, end)] = result
            return result
        
        return find_min_cost(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    # print ('Left', left_val, 'C', c)
                    right_val = dfs(c, end)
                    # print ('Right', right_val, 'C', c)
                    min_val = min(min_val, left_val + right_val)
                    # print (\"Left and Right\", left_val, right_val)
                    # print (\"MIN VAL:n \", min_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]

        cache = defaultdict(int)
        return dfs(0, n)

from collections import defaultdict

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]

        cache = defaultdict(int)
        return dfs(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        return self.dp(0, n, cuts, dict())
    
    def dp(self, i, j, cuts, memo):
        if (i, j) not in memo:
            minV = float('inf')
            for k in cuts:
                if k > i and k < j: # Valid cutting point
                    l, r = self.dp(i, k, cuts, memo), self.dp(k, j, cuts, memo)
                    minV = min(minV, l+r)
            if minV != float('inf'):
                memo[(i, j)] = minV+j-i
            else:
                memo[(i, j)] = 0
        return memo[(i, j)]

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        visited = {}  # map (start, end) -> min cost
        
        def minCostHelper(start, end):            
            # check if cached
            if (start, end) in visited:
                return visited[(start, end)]
            
            # if not, calculate
            min_cost = float('inf')
            for c in cuts:
                if c <= start or c >= end:
                    continue
                cost = (end-start) + minCostHelper(start, c) + minCostHelper(c, end)
                min_cost = min(min_cost, cost)
                
            if min_cost == float('inf'):
                min_cost = 0
                
            visited[(start, end)] = min_cost
            return min_cost
        
        return minCostHelper(0, n)


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        if cuts==None or len(cuts)==0:
            return 0
        
        N = len(cuts)
        if N==1:
            return n
        
        dp = defaultdict(int)
        def dfs(start, end):
            if (start, end) in dp:
                return dp[(start, end)]
            
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                dp[(start, end)] = 0
            else:
                dp[(start, end)] = end - start + min_val
            return dp[(start, end)]

        return dfs(0, n)     
        

                    
        


import sys
class Solution:
    def rec(self,l,h,cuts,dp):
        if h in dp[l]:
            return dp[l][h] 
        ans=sys.maxsize
        for i in cuts:
            if l<i and i<h:
                if i in dp[l]:
                    k1=dp[l][i]
                else:
                    k1=self.rec(l,i,cuts,dp)
                if h in dp[i]:
                    k2=dp[i][h]
                else:
                    k2=self.rec(i,h,cuts,dp)
                ans=min(ans,h-l+k1+k2)
        if ans==sys.maxsize:
            ans=0
        dp[l][h]=ans
        return dp[l][h]
                
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp={}
        for i in range(n+1):
            dp[i]={}
        return self.rec(0,n,cuts,dp)


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        return self.dp(0, n, cuts, dict())
    def dp(self, i, j, cuts, memo):
        if (i, j) not in memo:
            minV = float('inf')
            for k in cuts:
                if k > i and k < j: # Valid cutting point
                    l, r = self.dp(i, k, cuts, memo), self.dp(k, j, cuts, memo)
                    minV = min(minV, l+r)
            if minV != float('inf'):
                memo[(i, j)] = minV+j-i
            else:
                memo[(i, j)] = 0
        return memo[(i, j)]

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        mem = collections.defaultdict()
        
        def dp(i, j):
            if (i, j) in mem:
                return mem[(i,j)]
            ans = float('inf')
            can_cut = False
            for c in cuts:
                if i < c < j:
                    ans = min(ans, dp(i, c) + dp(c, j) + j - i)
                    can_cut = True
            if not can_cut:
                ans = 0
            mem[(i,j)] = ans
            return ans
        
        ans = dp(0, n)
        # print(mem)
        return ans

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        visited = {}  # map (start, end) -> min cost
        
        def minCostHelper(start, end):            
            # check if cached
            if (start, end) in visited:
                return visited[(start, end)]
            
            # if not, calculate
            min_cost = float('inf')
            for c in cuts:
                if c <= start or c >= end:
                    continue
                cost = (end-start) + minCostHelper(start, c) + minCostHelper(c, end)
                min_cost = min(min_cost, cost)
                
            # no cuts between start and end
            if min_cost == float('inf'):
                min_cost = 0
                
            visited[(start, end)] = min_cost
            return min_cost
        
        return minCostHelper(0, n)


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp = {}
        return self.recur(0,n, dp, cuts)
    
    def recur(self,l, r, dp, cuts):
        if (l,r) in dp:
            return dp[(l,r)]
        
        cost = r - l
        res = float('inf')
        for c in cuts:
            if c > l and c < r:
                res = min(res, self.recur(l,c,dp,cuts) + self.recur(c,r,dp,cuts) + cost)
                
        if res == float('inf'):
            dp[(l,r)] = 0
        else:
            dp[(l,r)] = res
            
        return dp[(l,r)]
        
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp = {}
        return self.recur(0,n, dp, cuts)
    
    def recur(self,l, r, dp, cuts):
        if (l,r) in dp:
            return dp[(l,r)]
        
        cost = r - l
        res = float('inf')
        for c in cuts:
            if c > l and c < r:
                res = min(res, self.recur(l,c,dp,cuts) + self.recur(c,r,dp,cuts) + cost)
                
        if res == float('inf'):
            res = 0
            
        dp[(l,r)] = res
        return dp[(l,r)]
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp = {}
        def dfs(i,j):
            if(i>j):
                return 0
            if((i,j) in dp):
                return dp[(i,j)]
            ans = float('inf')
            iscut = False;
            for cut in cuts:
                if(i<cut and j>cut):
                    temp = dfs(i,cut) + dfs(cut,j)
                    ans = min(temp, ans)
                    iscut = True
            if(not iscut):
                dp[(i,j)] = 0;
            else:
                dp[(i,j)] = ans + j-i;
            return dp[(i,j)]
        return dfs(0,n)


import sys
class Solution:
    def __init__(self):
        self.dp = {}
    def minCost(self, A: int, B: List[int]) -> int:
        self.set1 = set(B)
        def helper(st,end):
            if (st,end) in self.dp:
                return self.dp[(st,end)]
            if end-st ==1:
                return 0
            t = sys.maxsize
            for i in B:
                if i>st and i<end:
                    t = min(t,end-st+helper(st,i)+helper(i,end))
            self.dp[st,end] = (t if t != sys.maxsize else 0)
            return self.dp[(st,end)]
        
        helper(0,A)
        return self.dp[0,A]
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.append(0)
        cuts.append(n)
        cuts.sort()
        neighbor = dict()
        for i, cut in enumerate(cuts):
            if i == 0:
                neighbor[cut] = [None, cuts[i + 1]]
            elif i == len(cuts) - 1:
                neighbor[cut] = [cuts[i - 1], None]
            else:
                neighbor[cut] = [cuts[i - 1], cuts[i + 1]]
        
        cache = dict()
        # left, right are exclusive
        def search(left: int, right: int) -> int:
            if (left, right) in cache:
                return cache[(left, right)]
            
            min_cost = None
            for cut in cuts:
                if cut <= left or cut >= right:
                    continue
                leftnei, rightnei = neighbor[cut]
                # neighbor[leftnei][1] = rightnei
                # neighbor[rightnei][0] = leftnei
                
                cost = right - left
                cost += search(left, cut)
                cost += search(cut, right)
                min_cost = cost if min_cost is None else min(min_cost, cost)
                
                # neighbor[leftnei][1] = cut
                # neighbor[rightnei][0] = cut
                
            if min_cost is None:
                min_cost = 0
            cache[(left, right)] = min_cost
            return min_cost
        
        ans = search(0, n)
        # print(cache)
        return ans

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp={}
        position={}
        # for i in range(len(cuts)):
        #     position[cuts[i ]]=i
        cuts.sort()
        def f(s,e):
            if (s,e) in dp:
                return dp[(s,e)]
            else:
                res=float('inf')
                i=0
                while i<len(cuts) and cuts[i]<=s:
                    i+=1
                # print(\"i\"+str(i))
                j=len(cuts)-1
                while cuts[j]>=e and j>=0:
                    j-=1
                # print(j)
                if i>j:
                    dp[(s,e)]=0
                    return 0
                for k in range(i,j+1):
                    # dp[(s,e)]=dp[(s,cuts[k])]+dp[(cuts[k],e )]  +s-e
                    res=min(res,f(s,cuts[k])+f(cuts[k],e)+e-s)
                dp[(s,e)]=res
                return dp[(s,e)]

        return f(0,n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        self.memo = {}
        cuts = set(cuts)

        def dp(i, j):
            if (i, j) in self.memo:
                return self.memo[(i, j)]
            min_value = None
            for cut in cuts:
                if (cut > i) and (cut < j):
                    if min_value is None:
                        min_value = dp(i, cut) + dp(cut, j) + (j - i)
                    else:
                        min_value = min(min_value, dp(i, cut) + dp(cut, j) + (j-i))

            if min_value is None:
                min_value = 0
            self.memo[(i, j)] = min_value
            return min_value

        return dp(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        @lru_cache(None)
        def dfs(i,j):
            if i==j:
                return 0
            tot = float('inf') 
            for k in range(len(cuts)):
                if i<cuts[k]<j:
                    tot = min(tot, dfs(i, cuts[k])+dfs(cuts[k],j)+j-i)    
            if tot == float('inf'):
                return 0
            return tot
        return dfs(0,n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        dp = {}
        def minCostij(i, j):
            if (i,j) in dp:
                return dp[(i,j)]
            if i + 1 == j or i == j:
                dp[(i,j)] = 0
            else:
                minCosts = [minCostij(i,k) + minCostij(k,j) for k in cuts if (k < j and k > i)]
                if minCosts:
                    dp[(i,j)] = min(minCosts) + (j-i)
                else:
                    dp[(i,j)] = 0
            return dp[(i,j)]
        return minCostij(0,n)


from collections import defaultdict

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            min_val = float('inf')
            cut_found = False
            for c in cuts:
                if c > start and c < end: # Important!!! check the boundary condition
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                
            if not cut_found: # If no cut is found we know that the stick cannot be split more
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]

        cache = defaultdict()
        return dfs(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        self.memo = {}
        # self.memo[(i, j)]表示把i~j切成最小需要最少cost 
        self.helper(0, n, cuts)
        return self.memo[(0, n)]
    
    def helper(self, left, right, candidates):
        if left >= right:
            return 0
        
        if (left, right) in self.memo:
            return self.memo[(left, right)]
        
        res = sys.maxsize
        for k in candidates:
            if k <= left or k >= right:
                continue
                
            left_cost = self.helper(left, k, candidates)
            right_cost = self.helper(k, right, candidates)
            cost = right - left
            
            res = min(res, left_cost + right_cost + cost)
        
        
        if res == sys.maxsize:
            res = 0
        self.memo[(left, right)] = res
        return res

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        # cut.append(0)
        # cuts.append(n)
        # cuts.sort()
        return self.dfs(cuts, 0, n, dict())
    def dfs(self, cuts, i, j, memo):
        if j-i <= 1: return 0
        if (i, j) not in memo:
            memo[(i, j)] = float('inf')
            for c in cuts:
                if c > i and c < j:
                    memo[(i, j)] = min(memo[(i, j)], j-i+self.dfs(cuts, i, c, memo)+self.dfs(cuts, c, j, memo))
            if memo[(i, j)] == float('inf'):
                memo[(i, j)] = 0
        return memo[(i, j)]


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        return self.cut(0, n, set(cuts), {}) 
        
    def cut(self, i, j, cuts, dp):
        v = float('inf')
        if (i, j) in dp:
            return dp[(i, j)]
        for x in cuts:
            if i < x and j > x:
                v = min(v, j - i + self.cut(i, x, cuts, dp) + self.cut(x, j, cuts, dp))
        dp[(i, j)] = v if v != float('inf') else 0
        return dp[(i, j)]

from collections import defaultdict
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cache = defaultdict(int)
        
        def dfs(start, end):
            if (start, end) in cache:
                return cache[(start, end)]
            
            min_val = float('inf')
            cut_found = False
            
            for c in cuts:
                if c > start and c < end:
                    left_val = dfs(start, c)
                    right_val = dfs(c, end)
                    min_val = min(min_val, left_val + right_val)
                    cut_found = True
                    
            if not cut_found:
                cache[(start, end)] = 0
            else:
                cache[(start, end)] = end - start + min_val
            return cache[(start, end)]
        
        return dfs(0, n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        memo = {}
        
        def dp(start,end):
            if (start,end) in memo:
                return memo[(start,end)]
            
            ans = sys.maxsize
            canCut = False
            for cut in cuts:
                if start<cut<end:
                    canCut = True
                    ans = min(ans, dp(start,cut) + dp(cut,end) + (end-start))
                    
            if not canCut:
                return 0
            
            memo[(start,end)] = ans
            
            return ans
    
        return dp(0,n)


class Solution:
    def helper(self,B,s,e,d):
        
        if len(B)==0:
            d[(s,e)]=0
            return 0
            
        if (s,e) in d:
            return d[(s,e)]
        
        
        cost=e-s
        m=2**31-1
        for i in range(len(B)):
            m=min(m,self.helper(B[:i],s,B[i],d)+self.helper(B[i+1:],B[i],e,d))
            
        d[(s,e)]=cost+m
        
        return cost+m
    
    def minCost(self, n: int, cuts: List[int]) -> int:
       
        cuts.sort()
        d={}
        k=self.helper(cuts,0,n,d)
        return k


from math import inf
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def recurse(l,r):
            # if r<=l:
            #     return inf
            if self.dp.get((l,r),-1)!=-1:
                return self.dp[(l,r)]
            mnCut=inf
            flag=1
            for i in range(len(cuts)):
                if l<cuts[i]<r:
                    mnCut=min(mnCut,recurse(l,cuts[i])+recurse(cuts[i],r))
                    flag=0
            if flag==0:
                self.dp[(l,r)]=mnCut+r-l
            else:
                self.dp[(l,r)]=0
            return self.dp[(l,r)]
        self.dp={}
        cuts.sort()
        mn=recurse(0,n)
        # print(self.dp)
        return mn

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        
        def dp(s,e):
            if (s,e) in memo:
                return memo[(s,e)]
            ans=2**31
            # print(ans)
            canCut=False
            for cut in cuts:
                # canCut=True
                if s<cut<e:
                    canCut=True
                    a1=dp(s,cut)+dp(cut,e)+e-s
                    # print(a1)
                    ans=min(ans,a1)
            if not canCut:
                # print(\"in\")
                return 0
            memo[(s,e)]=ans
            return ans
        
        memo={}
        return dp(0,n)
        # return count
                    


class Node:
    def __init__(self, idx, l, r):
        self.idx = idx
        self.l = l
        self.r = r
        self.left_node = self
        self.right_node = self
        

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
    
        solved = dict()
    
        def cost(l, r):
            if l == r: return 0
            if (l, r) in solved:
                return solved[(l, r)]
            
            min_cost = float('inf')
            for c in cuts:
                if c > l and c < r:
                    min_cost = min(min_cost, r - l + cost(l, c) + cost(c, r))
            
            if min_cost == float('inf'): return 0
            
            solved[(l, r)] = min_cost
            return min_cost
        
        return cost(0, n)
        
        
'''

cost(0, l - 1) -> min(cost(0, r) + cost(r, l - 1)) for r in cuts


'''
        


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        return self.dp(cuts, 0, n, dict())
    
    def dp(self, cuts, a, b, memo):
        if (a, b) not in memo:
            memo[(a, b)], minV = float('inf'),float('inf')
            for j, c in enumerate(cuts):
                if c > a and c < b:
                    l, r = self.dp(cuts, a,c,memo), self.dp(cuts, c,b,memo)
                    memo[(a, b)] = min(memo[(a, b)], b-a)
                    minV = min(minV, l+r)
            if memo[(a, b)] == float('inf'):
                memo[(a, b)] = 0
            else:
                memo[(a, b)] += minV
        return memo[(a, b)]

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        # cuts.append(0)
        # cuts.append(n)
        # cuts.sort()
        return self.dp(cuts, 0, n, dict())
    
    def dp(self, cuts, a, b, memo):
        if (a, b) not in memo:
            memo[(a, b)], minV = float('inf'),float('inf')
            for j, c in enumerate(cuts):
                if c > a and c < b:
                    l, r = self.dp(cuts, a,c,memo), self.dp(cuts, c,b,memo)
                    memo[(a, b)] = min(memo[(a, b)], b-a)
                    minV = min(minV, l+r)
            if memo[(a, b)] == float('inf'):
                memo[(a, b)] = 0
            else:
                memo[(a, b)] += minV
        return memo[(a, b)]

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
#         cuts = sorted(cuts)
#         options = []
#         cuts = [0]+cuts+[n]
#         N = len(cuts)
#         for i in range(1, N):
#             options.append([cuts[i-1], cuts[i]])
        
#         val = 0
#         while len(options) != 1:
#             short_i = 0
#             min_wid = math.inf
#             for i in range(len(options)-1):
#                 a = options[i]
#                 b = options[i+1]
#                 if (a[1]-a[0]) + (b[1]-b[0]) < min_wid:
#                     short_i = i
#                     min_wid = (a[1]-a[0]) + (b[1]-b[0])
                    
#             val += min_wid
#             options[short_i][1] = options[short_i+1][1]
#             del options[short_i+1]
            
#         return val
            
        
        cuts = sorted(cuts)
        memo = {}
        t_cuts = [0]+cuts+[n]
        N = len(t_cuts)
        for i in range(1, N):
            memo[(t_cuts[i-1], t_cuts[i])] = 0
            
        def dp(s, e):
            # print((s,e), memo[(s,e)] if (s,e) in memo else False)
            if (s, e) in memo:
                return memo[(s,e)]
            
            
            filtered_cuts = [cut for cut in cuts if cut > s and cut < e]
            if len(filtered_cuts) == 0: 
                return 0
            
            ans = math.inf
            for cut in filtered_cuts:
                ans = min(ans, (e-s) + dp(s, cut) + dp(cut, e))
            
            memo[(s,e)] = ans
            return memo[(s,e)]
        
        
        ans =  dp(0, n)
        # print(memo)
        return ans

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.sort()
        def helper(cuts,memo,l,r):
            res=float('inf')
            key=(l,r)
            if key in memo.keys():
                return memo[key]
            for i in range(len(cuts)):
                if cuts[i]<=l or cuts[i]>=r: continue
                cost=r-l
                res=min(helper(cuts,memo,l,cuts[i])+cost+helper(cuts,memo,cuts[i],r),res)
            if res==float('inf'):
                res=0
            memo[key]=res
            return res
            
        c=collections.defaultdict(int)    
        return helper(cuts,c,0,n)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dp(i, j, memo):
            if (i, j) not in memo:
                if j-i <= 1: return 0
                memo[(i, j)] = float('inf')
                for c in cuts:
                    if c > i and c < j:
                        memo[(i, j)] = min(memo[(i, j)], j-i+dp(i, c, memo)+dp(c, j, memo))
            return memo[(i, j)] if memo[(i, j)] != float('inf') else 0
        return dp(0, n, dict())

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
#         for total length, find the location closest to center and cut it
#         remove that location from cuts and move on to the parts
#         sort the cuts array, easy to find mid that way
        
#         cuts.sort()
#         def cut(start, end, cuts, cuts_start, cuts_end):
#             print(start, end, cuts_start, cuts_end)
#             if end <= start or cuts_start > cuts_end:
#                 return 0
            
#             mid = (start + end) // 2
#             loc = bisect.bisect_left(cuts, mid, cuts_start, cuts_end)
            
#             print('loc', loc)
#             if loc >= len(cuts):
#                 return 0
            
#             left = cut(start, cuts[loc], cuts, cuts_start, loc - 1)
#             right = cut(cuts[loc], end, cuts, loc + 1, cuts_end)
#             print('price',(end - start), left , right)
#             v =  (end - start) + left + right
#             return v
        
#         print(cuts)
#         return cut(0, n, cuts, 0, len(cuts))
# TLE
#         def top_down(low, high, cuts):
#             possible_cuts = [c for c in cuts if low < c < high]
#             # print(possible_cuts)
#             if not possible_cuts:
#                 return 0
#             ans = float('inf')
#             for mid in possible_cuts:
#                 ans = min(ans, top_down(low, mid, cuts) + top_down(mid, high, cuts))
#             return ans + high - low
        
#         return top_down(0, n, cuts)
        dp = {}
        def top_down(low, high, cuts):
            if (low, high) in dp:
                return dp[(low, high)]
            
            possible_cuts = [c for c in cuts if low < c < high]
            # print(possible_cuts)
            if not possible_cuts:
                return 0
            ans = float('inf')
            for mid in possible_cuts:
                ans = min(ans, top_down(low, mid, cuts) + top_down(mid, high, cuts))
            dp[(low, high)] = ans + high - low
            return dp[(low, high)]
        
        return top_down(0, n, cuts)
            


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def dfs(i, j, memo):
            if (i, j) not in memo:
                if j-i <= 1: return 0
                memo[(i, j)] = float('inf')
                for c in cuts:
                    if c > i and c < j:
                        memo[(i, j)] = min(memo[(i, j)], j-i+dfs(i, c, memo)+dfs(c, j, memo))
            return memo[(i, j)] if memo[(i, j)] != float('inf') else 0
        return dfs(0, n, dict())

class Solution:
    def cal(self, i, j, cuts):
        if i in self.dp:
            if j in self.dp[i]:
                return self.dp[i][j]
        ans = float('inf')
        cost = j - i
        found = False
        for ind, c in enumerate(cuts):
            if i < c and c < j:
                t = cuts[:]
                del t[ind]
                ans = min(ans, cost + self.cal(i, c, t) + self.cal(c, j, t))
                found = True
        if not found:
            ans = 0
        if i in self.dp:
            self.dp[i][j] = ans
        else:
            self.dp[i] = {j: ans}
        return ans
    
    def minCost(self, n: int, cuts: List[int]) -> int:
        self.dp = {}
        return self.cal(0, n, sorted(cuts))

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        # cut.append(0)
        # cuts.append(n)
        # cuts.sort()
        return self.dfs(cuts, 0, n, dict())
    def dfs(self, cuts, i, j, memo):
        if j-i <= 1: return 0
        if (i, j) not in memo:
            memo[(i, j)] = float('inf')
            for c in cuts:
                if c > i and c < j:
                    memo[(i, j)] = min(memo[(i, j)], j-i+self.dfs(cuts, i, c, memo)+self.dfs(cuts, c, j, memo))                     
        return memo[(i, j)] if memo[(i, j)] != float('inf') else 0


import itertools
import sys
from functools import lru_cache
from math import comb
from typing import List

'''
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。定义切割成本是要切割的棍子长度，求最小的切割成本，即找到一个最小成本的切割顺序


n = 7, cuts = [1,3,4,5]
0 1| 2 3| 4| 5| 6 7

dfs:
        a
      b c d
      
dp[start][end]= min(dp[start][cut] + dp[cut][end])
斜向上扫描。


'''


class Solution1:
    def dfs(self, start, end, path, cuts):
        if self.dp[start][end] != sys.maxsize:
            return self.dp[start][end]
        min_cut = sys.maxsize
        flag = False
        nums = cuts[self.cuts_map[start]:self.cuts_map[end]]
        for cut in nums:
            if cut not in path and start < cut and cut < end:
                flag = True
                path.add(cut)
                min_cut = min(min_cut, end - start + self.dfs(start, cut, path, cuts) + self.dfs(cut, end, path, cuts))
                path.remove(cut)
        # 如果没切割点则返回0
        if not flag:
            min_cut = 0
        self.dp[start][end] = min_cut
        return min_cut

    def minCost(self, n: int, cuts: List[int]) -> int:
        self.dp = [[sys.maxsize for _ in range(n + 1)] for _ in range(n + 1)]
        cuts = sorted(cuts)
        self.cuts_map = {}
        for i, cut in enumerate(cuts):
            self.cuts_map[cut] = i
        self.cuts_map[0] = 0
        self.cuts_map[n] = n
        return self.dfs(0, n, set(), cuts)

    
class Solution:
    def dfs(self, start, end, path, cuts):
        if self.dp[self.cuts_map[start]][self.cuts_map[end]] != sys.maxsize:
            return self.dp[self.cuts_map[start]][self.cuts_map[end]]
        min_cut = sys.maxsize
        flag = False
        nums = cuts[self.cuts_map[start]:self.cuts_map[end]]
        for cut in nums:
            if cut not in path and start < cut and cut < end:
                flag = True
                path.add(cut)
                min_cut = min(min_cut, end - start + self.dfs(start, cut, path, cuts) + self.dfs(cut, end, path, cuts))
                path.remove(cut)
        # 如果没切割点则返回0
        if not flag:
            min_cut = 0
        self.dp[self.cuts_map[start]][self.cuts_map[end]] = min_cut
        return min_cut

    def minCost(self, n: int, cuts: List[int]) -> int:
        self.dp = [[sys.maxsize for _ in range(len(cuts) + 2)] for _ in range(len(cuts) + 2)]  # 内存太大，需要优化
        cuts.extend([0, n])
        cuts = sorted(cuts)
        self.cuts_map = {}
        for i, cut in enumerate(cuts):
            self.cuts_map[cut] = i
        return self.dfs(0, n, set(), cuts)

class Solution:
    def cal(self, i, j, cuts):
        if i in self.dp:
            if j in self.dp[i]:
                return self.dp[i][j]
        ans = float('inf')
        cost = j - i
        found = False
        for ind, c in enumerate(cuts):
            if i < c and c < j:
                t = cuts[:]
                del t[ind]
                ans = min(ans, cost + self.cal(i, c, t) + self.cal(c, j, t))
                found = True
        if not found:
            ans = 0
        if i in self.dp:
            self.dp[i][j] = ans
        else:
            self.dp[i] = {j: ans}
        return ans
    
    def minCost(self, n: int, cuts: List[int]) -> int:
        self.dp = {}
        return self.cal(0, n, cuts)

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        def top_down(i, j, memo):
            if (i, j) not in memo:
                # If length of current stick is less than or equal to one, we can't cut any further so cost will be zero.
                if j-i <= 1: return 0
                memo[(i, j)] = float('inf')
                for c in cuts:
                    # If c is not in the range of (i, j) exclusive, cut cannot be performed.
                    if c > i and c < j:
                        memo[(i, j)] = min(memo[(i, j)], j-i+top_down(i, c, memo)+top_down(c, j, memo))
            # if no valid cutting position, return 0 otherwise return optmal solution.
            return memo[(i, j)] if memo[(i, j)] != float('inf') else 0
        return top_down(0, n, dict())