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.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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):
			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
			return res
		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)


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 = 4294967295
			for c in cuts:
				if l < c < r:
					m = min(m, dfs(l, c) + dfs(c, r))
			return 0 if m == 4294967295 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):
			l = bin_search(st, '+')
			r = bin_search(end, '-')
			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):
		if j - i < 2:
			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:
			return 0
		result = min(options)
		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 = 1000000000.0
			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
				j = len(cuts) - 1
				if e > cuts[len(cuts) - 1]:
					j = len(cuts) - 1
				else:
					j = position[e] - 1
				if i > j:
					dp[s, e] = 0
					return 0
				for k in range(i, j + 1):
					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:
					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]
		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:
					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:
				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:
		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:
					(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 = {}

		def minCostHelper(start, end):
			if (start, end) in visited:
				return visited[start, end]
			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)


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:
		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)
		return ans


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 = {}

		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()

		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]
				cost = right - left
				cost += search(left, cut)
				cost += search(cut, right)
				min_cost = cost if min_cost is None else min(min_cost, cost)
			if min_cost is None:
				min_cost = 0
			cache[left, right] = min_cost
			return min_cost
		ans = search(0, n)
		return ans


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)


class Solution:

	def minCost(self, n: int, cuts: List[int]) -> int:
		self.memo = {}
		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:
		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]


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 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)
		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
			canCut = False
			for cut in cuts:
				if s < cut < e:
					canCut = True
					a1 = dp(s, cut) + dp(cut, e) + e - s
					ans = min(ans, a1)
			if not canCut:
				return 0
			memo[s, e] = ans
			return ans
		memo = {}
		return dp(0, n)


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)


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 = 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):
			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)
		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:
		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]
			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 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))


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

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)
		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)
		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)