Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.
Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1.
Example 1:
Input:
n = 2
keys = {10, 12}
freq = {34, 50}
Output: 118
Explaination:
There can be following two possible BSTs 
        10                       12
          \                     / 
           12                 10
                              
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118 
Example 2:
Input:
N = 3
keys = {10, 12, 20}
freq = {34, 8, 50}
Output: 142
Explaination: There can be many possible BSTs
     20
    /
   10  
    \
     12  
     
Among all possible BSTs, 
cost of this BST is minimum.  
Cost of this BST is 1*50 + 2*34 + 3*8 = 142
Your Task:
You don't need to read input or print anything. Your task is to complete the function optimalSearchTree() which takes the array keys[], freq[] and their size n as input parameters and returns the total cost of all the searches is as small as possible.
Expected Time Complexity: O(n^{3})
Expected Auxiliary Space: O(n^{2})
Constraints:
1 ≤ N ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Range queries

Starter code: #User function Template for python3

class Solution:
    def optimalSearchTree(self, keys, freq, n):
        # code here

Solutions:
class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			for (i, j) in zip(range(n - g), range(g, n)):
				if g == 0:
					dp[i][j] = freq[i]
				if g == 1:
					dp[i][j] = min(2 * freq[i] + freq[j], 2 * freq[j] + freq[i])
				else:
					mini = 99999999999999
					sumi = 0
					for x in range(i, j + 1):
						sumi += freq[x]
					for k in range(i, j + 1):
						left = 0 if k == i else dp[i][k - 1]
						right = 0 if k == j else dp[k + 1][j]
						if left + right + sumi < mini:
							mini = left + right + sumi
					dp[i][j] = mini
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [['.'] * n for i in range(n)]
		for g in range(n):
			for (i, j) in zip(range(n - g), range(g, n)):
				if g == 0:
					dp[i][j] = freq[i]
				elif g == 1:
					f1 = freq[i]
					f2 = freq[j]
					dp[i][j] = min(f1 + 2 * f2, 2 * f1 + f2)
				else:
					Min = 10000000000.0 + 7
					freqSum = 0
					for x in range(i, j + 1):
						freqSum += freq[x]
					for k in range(i, j + 1):
						if k == i:
							left = 0
						else:
							left = dp[i][k - 1]
						if k == j:
							right = 0
						else:
							right = dp[k + 1][j]
						if left + right + freqSum < Min:
							Min = left + right + freqSum
					dp[i][j] = Min
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		cost = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			cost[i][i] = freq[i]
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				offsetsum = sum(freq[i:j + 1])
				cost[i][j] = float('inf')
				for root in range(i, j + 1):
					c = 0
					if root > i:
						c += cost[i][root - 1]
					if root < j:
						c += cost[root + 1][j]
					c += offsetsum
					cost[i][j] = min(cost[i][j], c)
		return cost[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		cost = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			cost[i][i] = freq[i]
		for L in range(2, n + 1):
			for i in range(n - L + 1):
				j = i + L - 1
				offsetSum = sum(freq[i:j + 1])
				cost[i][j] = float('inf')
				for r in range(i, j + 1):
					c = 0
					if r > i:
						c += cost[i][r - 1]
					if r < j:
						c += cost[r + 1][j]
					c += offsetSum
					if c < cost[i][j]:
						cost[i][j] = c
		return cost[0][n - 1]


class Solution:

	def cost(self, arr, i, j):
		count = 0
		while i <= j:
			count += arr[i]
			i += 1
		return count

	def helper(self, i, j, freq, mem):
		if i > j:
			return 0
		key = str(i) + ':' + str(j)
		if key in mem:
			return mem[key]
		cost = self.cost(freq, i, j)
		ans = float('inf')
		for k in range(i, j + 1):
			temp_ans = cost + self.helper(i, k - 1, freq, mem) + self.helper(k + 1, j, freq, mem)
			ans = min(ans, temp_ans)
		mem[key] = ans
		return ans

	def optimalSearchTree(self, keys, freq, n):
		mem = {}
		return self.helper(0, n - 1, freq, mem)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		cost = [[0 for x in range(n)] for y in range(n)]
		for i in range(n):
			cost[i][i] = freq[i]
		for L in range(2, n + 1):
			for i in range(n - L + 2):
				j = i + L - 1
				if i >= n or j >= n:
					break
				off_set_sum = self.sum(freq, i, j)
				cost[i][j] = 10 ** 10
				for r in range(i, j + 1):
					c = 0
					if r > i:
						c += cost[i][r - 1]
					if r < j:
						c += cost[r + 1][j]
					c += off_set_sum
					if c < cost[i][j]:
						cost[i][j] = c
		return cost[0][n - 1]

	def sum(self, freq, i, j):
		s = 0
		for k in range(i, j + 1):
			s += freq[k]
		return s


from math import inf

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		sums = [0 for i in range(n + 1)]
		for i in range(n):
			sums[i] = sums[i - 1] + freq[i]
		for i in range(n - 1, -1, -1):
			dp[i][i] = freq[i]
			for j in range(i + 1, n):
				dp[i][j] = inf
				for root in range(i, j + 1):
					dp[i][j] = min(dp[i][j], dp[i][root - 1] + dp[root + 1][j] + (sums[j] - sums[i] + freq[i]))
		return dp[0][-2]


import sys
from math import inf
sys.setrecursionlimit(1000000)

class Solution:

	def __optimal_search_tree(self, i, j, keys, freq):
		if i > j:
			return 0
		if i == j:
			return freq[i]
		if self.dp[i][j] == None:
			self.dp[i][j] = inf
			for root in range(i, j + 1):
				self.dp[i][j] = min(self.dp[i][j], self.__optimal_search_tree(i, root - 1, keys, freq) + self.__optimal_search_tree(root + 1, j, keys, freq) + (self.sums[j] - self.sums[i] + freq[i]))
		return self.dp[i][j]

	def optimalSearchTree(self, keys, freq, n):
		self.dp = [[None for j in range(n)] for i in range(n)]
		self.sums = [0 for i in range(n)]
		self.sums[0] = freq[0]
		for i in range(1, n):
			self.sums[i] = self.sums[i - 1] + freq[i]
		return self.__optimal_search_tree(0, n - 1, keys, freq)


import sys

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n:
				if g == 0:
					dp[i][j] = freq[i]
				elif g == 1:
					dp[i][j] = min(1 * freq[i] + 2 * freq[j], 1 * freq[j] + 2 * freq[i])
				else:
					freq_sum = 0
					min_cost = float('inf')
					for k in range(i, j + 1):
						left = dp[i][k - 1] if k > 0 else 0
						right = dp[k + 1][j] if k < j else 0
						freq_sum += freq[k]
						min_cost = min(min_cost, left + right)
					dp[i][j] = min_cost + freq_sum
				i += 1
				j += 1
		return dp[0][n - 1]


class Solution:

	def sumFreq(self, i, j, freq):
		su = 0
		for k in range(i, j + 1):
			su += freq[k]
		return su

	def solve(self, left, right, freq, dp):
		if left > right:
			return 0
		if dp[left][right] != -1:
			return dp[left][right]
		weight = self.sumFreq(left, right, freq)
		ans = 1000000000.0
		for i in range(left, right + 1):
			ans = min(ans, self.solve(left, i - 1, freq, dp) + self.solve(i + 1, right, freq, dp))
		dp[left][right] = ans + weight
		return dp[left][right]

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		return self.solve(0, n - 1, freq, dp)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			(r, c) = (0, i)
			while c < n:
				sm = sum(freq[r:c + 1])
				sub = float('INF')
				for curr in range(r, c + 1):
					left = 0
					right = 0
					if curr - 1 >= r:
						left = dp[r][curr - 1]
					if curr + 1 <= c:
						right = dp[curr + 1][c]
					sub = min(sub, left + right)
				if sub == float('INF'):
					sub = 0
				dp[r][c] = sm + sub
				r += 1
				c += 1
		return dp[0][n - 1]


from functools import lru_cache
from math import inf

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		pref = [0]
		for i in range(n):
			pref.append(pref[-1] + freq[i])

		@lru_cache(None)
		def dp(i, j):
			if i == j:
				return freq[i]
			best = min(dp(i, i) + dp(i + 1, j) + pref[j + 1] - pref[i + 1], dp(i, j - 1) + dp(j, j) + pref[j] - pref[i])
			for k in range(i + 1, j):
				best = min(best, freq[k] + dp(i, k - 1) + pref[k] - pref[i] + dp(k + 1, j) + pref[j + 1] - pref[k + 1])
			return best
		return dp(0, n - 1)


from functools import lru_cache
from math import inf

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		pref = [0]
		for i in range(n):
			pref.append(pref[-1] + freq[i])
		dp = [[inf] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = freq[i]
		for k in range(1, n):
			for i in range(n - k):
				j = i + k
				dp[i][j] = min(dp[i][i] + dp[i + 1][j] + pref[j + 1] - pref[i + 1], dp[i][j - 1] + dp[j][j] + pref[j] - pref[i])
				for x in range(i + 1, j):
					dp[i][j] = min(dp[i][j], dp[x][x] + dp[i][x - 1] + pref[x] - pref[i] + dp[x + 1][j] + pref[j + 1] - pref[x + 1])
		return dp[0][n - 1]


class Solution:

	def sumFreq(self, i, j, freq):
		Sum = 0
		for k in range(i, j):
			Sum += freq[k]
		return Sum

	def cost(self, i, j, freq, dp):
		if i >= j:
			dp[i][j] = 0
			return dp[i][j]
		if j - i == 1:
			dp[i][j] = freq[i]
			return dp[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		weight = self.sumFreq(i, j, freq)
		ans = float('inf')
		for k in range(i, j):
			temp = self.cost(i, k, freq, dp) + self.cost(k + 1, j, freq, dp)
			ans = min(ans, temp)
		dp[i][j] = ans + weight
		return dp[i][j]

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for j in range(n + 1)] for i in range(n + 1)]
		return self.cost(0, n, freq, dp)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		t = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		fsum = [0] * n
		fsum[0] = freq[0]
		for i in range(1, n):
			fsum[i] = freq[i] + fsum[i - 1]
		for gap in range(0, n):
			i = 0
			for j in range(gap, n):
				if gap == 0:
					t[i][j] = freq[i]
				elif gap == 1:
					v1 = freq[i]
					v2 = freq[j]
					t[i][j] = min(v1 + 2 * v2, v2 + v1 * 2)
				else:
					mn = 2147483647
					fs = fsum[j] - (0 if i == 0 else fsum[i - 1])
					for k in range(i, j + 1):
						left = 0 if k == i else t[i][k - 1]
						right = 0 if k == j else t[k + 1][j]
						if left + right + fs < mn:
							mn = left + right + fs
					t[i][j] = mn
				i += 1
		return t[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		n += 1
		p = [0]
		p.extend(freq)
		q = [0] * n
		e = [[float('inf')] * n for _ in range(n + 1)]
		w = [[0] * n for _ in range(n + 1)]
		for i in range(1, n + 1):
			w[i][i - 1] = q[i - 1]
			e[i][i - 1] = q[i - 1]
		for i in range(n - 1, 0, -1):
			for j in range(i, n):
				w[i][j] = w[i][j - 1] + p[j] + q[j]
				for k in range(i, j + 1):
					e[i][j] = min(e[i][j], e[i][k - 1] + e[k + 1][j] + w[i][j])
		return e[1][n - 1]


import sys
INT_MAX = sys.maxsize

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		pre_sum = [-1 for _ in range(n)]
		pre_sum[0] = freq[0]
		for i in range(1, n):
			pre_sum[i] = pre_sum[i - 1] + freq[i]
		for l in range(1, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				if l == 1:
					dp[i][j] = freq[i]
				elif l == 2:
					dp[i][j] = min(freq[i] + 2 * freq[j], 2 * freq[i] + freq[j])
				else:
					fs = pre_sum[j] if i == 0 else pre_sum[j] - pre_sum[i - 1]
					min_val = INT_MAX
					for k in range(i, j + 1):
						left = 0 if k == i else dp[i][k - 1]
						right = 0 if k == j else dp[k + 1][j]
						min_val = min(min_val, left + right + fs)
					dp[i][j] = min_val
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):

		def f(i, j, freq, keys, dp):
			if i > j:
				return 0
			if i == j:
				return freq[i]
			if dp[i][j] != -1:
				return dp[i][j]
			fsum = sum(freq[i:j + 1])
			mn = 1000000000.0
			for k in range(i, j + 1):
				mn = min(mn, f(i, k - 1, freq, keys, dp) + f(k + 1, j, freq, keys, dp) + fsum)
			dp[i][j] = mn
			return mn
		dp = [[-1] * n for p in range(n)]
		return f(0, n - 1, freq, keys, dp)


class Solution:

	def __init__(self):
		self.d = {}

	def optimalSearchTree(self, keys, freq, n):

		def f(fr, i, j):
			if i > j:
				return 0
			if i == j:
				return fr[i]
			if (i, j) in self.d.keys():
				return self.d[i, j]
			s = sum(fr[i:j + 1])
			minn = float('inf')
			for r in range(i, j + 1):
				cost = f(fr, i, r - 1) + f(fr, r + 1, j)
				minn = min(cost, minn)
			self.d[i, j] = minn + s
			return minn + s
		return f(freq, 0, n - 1)


class Solution:

	def optimalSearchTree(self, a, p, n):
		n += 1
		a.insert(0, 0)
		p.insert(0, 0)
		l = [[[0, 0] for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(n - i):
				k = j + i
				if i == 0:
					pass
				elif i == 1:
					l[j][k][0] = p[k]
					l[j][k][1] = l[j][k - 1][1] + l[k][k][1] + l[j][k][0]
				else:
					l[j][k][0] = l[j][k - 1][0] + p[k]
					m = 999999
					for x in range(j + 1, k + 1):
						y = l[j][x - 1][1] + l[x][k][1]
						if y < m:
							m = y
					l[j][k][1] = m + l[j][k][0]
		return l[0][n - 1][1]


def f(freq, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	cost = sum(freq[i:j + 1])
	ans = 1000000000.0
	for k in range(i, j + 1):
		c = cost + f(freq, i, k - 1, dp) + f(freq, k + 1, j, dp)
		ans = min(ans, c)
	dp[i][j] = ans
	return ans

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(n)] for i in range(n)]
		return f(freq, 0, n - 1, dp)


from functools import lru_cache

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1] * (n + 1) for i in range(n + 1)]

		def rec(start, end):
			if start > end:
				return 0
			if start == end:
				return freq[start]
			if dp[start][end] != -1:
				return dp[start][end]
			ans = 1000000000000.0
			for mid in range(start, end + 1):
				ans = min(ans, rec(start, mid - 1) + rec(mid + 1, end))
			for k in range(start, end + 1):
				ans += freq[k]
			dp[start][end] = ans
			return dp[start][end]
		return rec(0, n - 1)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[100000000 for _ in range(n)] for _ in range(n)]
		prefix_sum = [freq[i] for i in range(n)]
		dp[0][0] = freq[0]
		for i in range(1, n):
			prefix_sum[i] += prefix_sum[i - 1]
			dp[i][i] = freq[i]

		def sum_in_range(a, b):
			if a > b:
				return 0
			if a == 0:
				return prefix_sum[b]
			return prefix_sum[b] - prefix_sum[a - 1]
		i = 0
		for gap in range(1, n):
			for j in range(gap, n):
				for k in range(i, j + 1):
					left_tree_cnt = sum_in_range(i, k - 1) + dp[i][k - 1] if k > i else 0
					right_tree_cnt = sum_in_range(k + 1, j) + dp[k + 1][j] if k < j else 0
					dp[i][j] = min(dp[i][j], left_tree_cnt + freq[k] + right_tree_cnt)
				i += 1
			i = 0
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]

		def minCost(i, j):
			if i > j:
				return 0
			if i == j:
				return freq[i]
			if dp[i][j] != -1:
				return dp[i][j]
			mini = float('inf')
			s = 0
			for k in range(i, j + 1):
				s += freq[k]
			for k in range(i, j + 1):
				mini = min(mini, minCost(i, k - 1) + minCost(k + 1, j) + s)
			dp[i][j] = mini
			return mini
		return minCost(0, n - 1)


import math
import sys

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(n)] for j in range(n)]

		def minCost(i, j):
			if i > j:
				return 0
			if i == j:
				return freq[i]
			if dp[i][j] != -1:
				return dp[i][j]
			temp = math.inf
			s = 0
			for k in range(i, j + 1):
				s += freq[k]
			for k in range(i, j + 1):
				temp = min(temp, s + minCost(i, k - 1) + minCost(k + 1, j))
			dp[i][j] = temp
			return temp
		return minCost(0, n - 1)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n:
				if g == 0:
					dp[i][j] = freq[i]
				elif g == 1:
					dp[i][j] = min(2 * freq[j] + freq[i], freq[j] + 2 * freq[i])
				else:
					mini = float('inf')
					fSum = 0
					for m in range(i, j + 1):
						fSum += freq[m]
					for k in range(i, j + 1):
						left = dp[i][k - 1] if k != 0 else 0
						right = dp[k + 1][j] if k != n - 1 else 0
						mini = min(mini, left + right + fSum)
					dp[i][j] = mini
				j += 1
				i += 1
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		pref = [0]
		for i in range(0, n):
			pref.append(pref[-1] + freq[i])
		dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			c = 0
			for j in range(i, n + 1):
				m = 999999999
				for k in range(c, j):
					m = min(m, dp[c][k] + dp[k + 1][j] + pref[j] - pref[c])
				dp[c][j] = m
				c += 1
		return dp[0][n]


import sys
from sys import maxsize

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		freqSum = [0 for i in range(n)]
		freqSum[0] = freq[0]
		for i in range(1, n):
			freqSum[i] = freq[i] + freqSum[i - 1]
		cost = [[maxsize for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			cost[i][i] = freq[i]
		for size in range(2, n + 1):
			for startIdx in range(n - size + 2):
				endIdx = min(n - 1, startIdx + size - 1)
				for curr in range(startIdx, endIdx + 1):
					currTotalCost = 0
					if startIdx > 0:
						currTotalCost = freqSum[endIdx] - freqSum[startIdx - 1]
					else:
						currTotalCost = freqSum[endIdx]
					if curr != startIdx:
						currTotalCost += cost[startIdx][curr - 1]
					if curr != endIdx:
						currTotalCost += cost[curr + 1][endIdx]
					if currTotalCost < cost[startIdx][endIdx]:
						cost[startIdx][endIdx] = currTotalCost
		return cost[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[None] * n for _ in range(n)]

		def hi(l1, l2):
			if l2 < l1:
				return 0
			if l1 == l2:
				dp[l1][l1] = freq[l1]
				return freq[l1]
			else:
				if dp[l1][l2] != None:
					return dp[l1][l2]
				best = []
				s = sum(freq[l1:l2 + 1])
				for a in range(l1, l2 + 1):
					l = hi(l1, a - 1)
					m = hi(a, a)
					r = hi(a + 1, l2)
					best.append(l + r + s)
				dp[l1][l2] = min(best)
				return dp[l1][l2]
		return hi(0, n - 1)


def util(keys, freq, i, j, dp):
	if i < 0 or i >= n or j < 0 or (j >= n):
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	if i > j:
		dp[i][j] = 0
		return 0
	elif i == j:
		dp[i][j] = freq[i]
		return freq[i]
	res = float('inf')
	c = 0
	for k in range(i, j + 1):
		c += freq[k]
		cur = util(keys, freq, i, k - 1, dp) + util(keys, freq, k + 1, j, dp)
		res = min(res, cur)
	dp[i][j] = res + c
	return res + c

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for j in range(n)] for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(n):
				if i > j:
					dp[i][j] = 0
				elif i == j:
					dp[i][j] = freq[i]
				else:
					c = 0
					res = float('inf')
					for k in range(i, j + 1):
						c += freq[k]
						try:
							cur = dp[i][k - 1] + dp[k + 1][j]
						except IndexError as e:
							print(i, k - 1, k + 1, j, e)
						res = min(res, cur)
					dp[i][j] = res + c
		return dp[0][n - 1]
		dp = [[-1 for j in range(n)] for i in range(n)]
		return util(keys, freq, 0, n - 1, dp)


def util(keys, freq, i, j, dp):
	if i < 0 or i >= n or j < 0 or (j >= n):
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	if i > j:
		dp[i][j] = 0
		return 0
	elif i == j:
		dp[i][j] = freq[i]
		return freq[i]
	res = float('inf')
	c = 0
	for k in range(i, j + 1):
		c += freq[k]
		cur = util(keys, freq, i, k - 1, dp) + util(keys, freq, k + 1, j, dp)
		res = min(res, cur)
	dp[i][j] = res + c
	return res + c

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for j in range(n)] for i in range(n)]
		return util(keys, freq, 0, n - 1, dp)


from sys import maxsize

class Solution:

	def solve(self, i, j, dp, freq):
		if i > j:
			return 0
		if i == j:
			dp[i][j] = freq[i]
			return dp[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		ans = maxsize
		wt = sum(freq[i:j + 1])
		for k in range(i, j + 1):
			temp = self.solve(i, k - 1, dp, freq) + self.solve(k + 1, j, dp, freq)
			ans = min(ans, temp)
		dp[i][j] = ans + wt
		return dp[i][j]

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(n)] for j in range(n)]
		return self.solve(0, n - 1, dp, freq)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		memo = {}

		def optCost(freq, i, j):
			if j < i:
				return 0
			if j == i:
				return freq[i]
			if (i, j) in memo:
				return memo[i, j]
			fsum = sum(freq[i:j + 1])
			minval = float('inf')
			for r in range(i, j + 1):
				cost = optCost(freq, i, r - 1) + optCost(freq, r + 1, j)
				if cost < minval:
					minval = cost
			memo[i, j] = minval + fsum
			return memo[i, j]
		return optCost(freq, 0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


import sys

class Solution:

	def level_sum(self, i, j, freq):
		return sum(freq[i:j + 1])

	def util(self, i, j, freq, dp):
		if i > j:
			return 0
		if i == j:
			return freq[i]
		if dp[i][j] != -1:
			return dp[i][j]
		level_sum = self.level_sum(i, j, freq)
		temp = sys.maxsize
		for k in range(i, j + 1):
			curr = self.util(i, k - 1, freq, dp) + self.util(k + 1, j, freq, dp)
			temp = min(temp, curr)
		dp[i][j] = temp + level_sum
		return dp[i][j]

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1] * n for i in range(n)]
		return self.util(0, n - 1, freq, dp)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


import math

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		self.DP = [[-1] * n for _ in range(n)]

		def helper(i, j):
			if j < i:
				return 0
			if j == i:
				return freq[i]
			if self.DP[i][j] != -1:
				return self.DP[i][j]
			cost = math.inf
			total = findSum(i, j)
			for r in range(i, j + 1):
				temp = helper(i, r - 1) + helper(r + 1, j)
				cost = min(cost, temp)
			self.DP[i][j] = cost + total
			return cost + total

		def findSum(i, j):
			total = 0
			for k in range(i, j + 1):
				total += freq[k]
			return total
		return helper(0, len(freq) - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			for (i, j) in zip(range(n - g), range(g, n)):
				if g == 0:
					dp[i][j] = freq[i]
				if g == 1:
					dp[i][j] = min(2 * freq[i] + freq[j], 2 * freq[j] + freq[i])
				else:
					mini = 99999999999999
					sumi = 0
					for x in range(i, j + 1):
						sumi += freq[x]
					for k in range(i, j + 1):
						left = 0 if k == i else dp[i][k - 1]
						right = 0 if k == j else dp[k + 1][j]
						if left + right + sumi < mini:
							mini = left + right + sumi
					dp[i][j] = mini
		return dp[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		pref = [i for i in freq]
		for i in range(1, n):
			pref[i] += pref[i - 1]
		for g in range(n):
			i = 0
			j = i + g
			while j < n:
				if g == 0:
					dp[i][j] = freq[i]
				else:
					m = float('inf')
					for k in range(i, j + 1):
						l = dp[i][k - 1] if k - 1 >= 0 else 0
						r = dp[k + 1][j] if k + 1 < n else 0
						m = min(m, l + r)
					dp[i][j] = m + pref[j]
					if i != 0:
						dp[i][j] -= pref[i - 1]
				i += 1
				j += 1
		return dp[0][-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
		for i in range(n):
			dp[i][i] = 0
			dp[i][i + 1] = freq[i]
		dp[n][n] = 0
		for i in range(2, n + 1):
			for j in range(n - i + 1):
				mn = float('inf')
				for k in range(j + 1, j + i + 1):
					mn = min(mn, dp[j][k - 1] + dp[k][j + i])
				dp[j][j + i] = mn + sum(freq[j:j + i])
		return dp[0][n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		memo = {}

		def cost(si, ei):
			if (si, ei) in memo:
				return memo[si, ei]
			elif si == ei:
				return freq[si]
			elif si > ei:
				return 0
			sumx = sum(freq[si:ei + 1])
			minCost = float('inf')
			for i in range(si, ei + 1):
				minCost = min(minCost, cost(si, i - 1) + cost(i + 1, ei) + sumx)
			memo[si, ei] = minCost
			return minCost
		return cost(0, n - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


def sum(freq, i, j):
	s = 0
	for r in range(i, j + 1):
		s += freq[r]
	return s

def optCost(freq, i, j, costs):
	if i > j:
		return 0
	if costs[i][j] > 0:
		return costs[i][j]
	if i == j:
		return freq[i]
	min = 999999999
	fsum = sum(freq, i, j)
	for r in range(i, j + 1):
		cost = optCost(freq, i, r - 1, costs) + optCost(freq, r + 1, j, costs)
		if min > cost:
			min = cost
	costs[i][j] = fsum + min
	return costs[i][j]

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		n = len(freq)
		costs = [[-1] * n for i in range(n)]
		return optCost(freq, 0, n - 1, costs)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for gap in range(n):
			for j in range(gap, n):
				i = j - gap
				if gap == 0:
					dp[i][j] = freq[i]
				if gap == 1:
					dp[i][j] = min(1 * freq[i] + 2 * freq[j], 1 * freq[j] + 2 * freq[i])
				else:
					sum1 = 0
					mini = 10 ** 9
					for k in range(i, j + 1):
						sum1 += freq[k]
						if k != i:
							left = dp[i][k - 1]
						else:
							left = 0
						if k != j:
							right = dp[k + 1][j]
						else:
							right = 0
						mini = min(mini, left + right)
					dp[i][j] = mini + sum1
		return dp[0][n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		keys = input().split()
		for itr in range(n):
			keys[itr] = int(keys[itr])
		freq = input().split()
		for itr in range(n):
			freq[itr] = int(freq[itr])
		ob = Solution()
		print(ob.optimalSearchTree(keys, freq, n))


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		sum_ = [0] * n
		sum_[0] = freq[0]
		for i in range(1, n):
			sum_[i] = sum_[i - 1] + freq[i]
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			dp[i][i] = freq[i]
		for size in range(1, n):
			for i in range(n - size):
				dp[i][i + size] = float('inf')
				for j in range(i, i + size + 1):
					exp1 = (dp[i][j - 1] if j > 0 else 0) + freq[j] + (dp[j + 1][i + size] if j < n - 1 else 0)
					exp2 = (sum_[j - 1] if j > 0 else 0) - (sum_[i - 1] if i > 0 else 0) + (sum_[i + size] - sum_[j])
					dp[i][i + size] = min(dp[i][i + size], exp1 + exp2)
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			for (i, j) in zip(range(n - g), range(g, n)):
				if g == 0:
					dp[i][j] = freq[i]
				if g == 1:
					dp[i][j] = min(freq[i] + 2 * freq[j], freq[j] + 2 * freq[i])
				else:
					mini = float('inf')
					freq_sum = 0
					for x in range(i, j + 1):
						freq_sum += freq[x]
					for k in range(i, j + 1):
						left = 0 if k == i else dp[i][k - 1]
						right = 0 if k == j else dp[k + 1][j]
						if left + right + freq_sum < mini:
							mini = left + right + freq_sum
					dp[i][j] = mini
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in range(n):
				if i == j:
					dp[i][j] = freq[i]
		x = -1
		k = 1
		for i in range(n - 1):
			j = 0
			x += 1
			while j < n - 1 - x:
				if i == 0:
					dp[j][k] = min(dp[j][k - 1] * 1 + dp[j + 1][k] * 2, dp[j][k - 1] * 2 + dp[j + 1][k] * 1)
				else:
					extra = sum(freq[j:k + 1])
					min_c = float('inf')
					for y in range(j, k + 1):
						if y == 0:
							min_c = min(min_c, extra + 0 + dp[y + 1][k])
						elif y == n - 1:
							min_c = min(min_c, extra + dp[j][y - 1] + 0)
						else:
							min_c = min(min_c, extra + dp[j][y - 1] + dp[y + 1][k])
					dp[j][k] = min_c
				j += 1
				k += 1
			k = x + 2
		return dp[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for i in range(1001)] for j in range(1001)]

		def sumfreq(i, j):
			summ = 0
			for k in range(i, j + 1):
				summ += freq[k]
			return summ

		def solve(i, j):
			if i > j:
				return 0
			if i == j:
				return freq[i]
			if dp[i][j] != -1:
				return dp[i][j]
			weight = sumfreq(i, j)
			ans = float('inf')
			for k in range(i, j + 1):
				temp = solve(i, k - 1) + solve(k + 1, j)
				ans = min(ans, temp)
			dp[i][j] = ans + weight
			return dp[i][j]
		return solve(0, n - 1)


MAX = 10 ** 9 + 7

class Solution:

	def solve(self, keys, freq, i, j):
		if i > j:
			return 0
		elif self.dp[i][j] != -1:
			return self.dp[i][j]
		total = sum(freq[i:j + 1])
		cost = MAX
		for k in range(i, j + 1):
			if self.dp[i][k - 1] != -1:
				if self.dp[k + 1][j] != -1:
					temp = self.dp[i][k - 1] + self.dp[k + 1][j] + total
				else:
					temp = self.dp[i][k - 1] + self.solve(keys, freq, k + 1, j) + total
			elif self.dp[k + 1][j] != -1:
				temp = self.solve(keys, freq, i, k - 1) + self.dp[k + 1][j] + total
			else:
				temp = self.solve(keys, freq, i, k - 1) + self.solve(keys, freq, k + 1, j) + total
			cost = min(cost, temp)
		self.dp[i][j] = cost
		return cost

	def optimalSearchTree(self, keys, freq, n):
		self.dp = [[-1 for i in range(110)] for j in range(110)]
		return self.solve(keys, freq, 0, n - 1)


class Solution:

	def optimalSearchTree(self, keys, freq, n):

		def sum(i, j, freq):
			sum1 = 0
			for k in range(i, j + 1):
				sum1 += freq[k]
			return sum1
		dp = [[-1] * (n + 1) for j in range(n + 1)]

		def cost(i, j, freq):
			if i > j:
				return 0
			if i == j:
				dp[i][j] = freq[i]
			if dp[i][j] != -1:
				return dp[i][j]
			min1 = float('inf')
			weight = sum(i, j, freq)
			for k in range(i, j + 1):
				ans = cost(i, k - 1, freq) + cost(k + 1, j, freq)
				min1 = min(min1, ans)
			dp[i][j] = min1 + weight
			return dp[i][j]
		return cost(0, n - 1, freq)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		(keys, freq) = zip(*sorted(zip(keys, freq)))
		for g in range(n):
			for i in range(n - g):
				j = i + g
				if g == 0:
					dp[i][j] = freq[i]
				elif g == 1:
					f1 = freq[i]
					f2 = freq[j]
					dp[i][j] = min(2 * f1 + f2, 2 * f2 + f1)
				else:
					freq_sum = 0
					for x in range(i, j + 1):
						freq_sum += freq[x]
					min_v = float('inf')
					for k in range(i, j + 1):
						left = dp[i][k - 1] if k != i else 0
						right = dp[k + 1][j] if k != j else 0
						min_v = min(min_v, left + right)
					dp[i][j] = min_v + freq_sum
		return dp[0][n - 1]


from typing import List

def util(freq, i, j, level):
	if i > j:
		return 0
	if util.mem[i][j] != None:
		(l, cost) = util.mem[i][j]
		if l <= level:
			return cost + (level - l) * (freq[j] + util.prefixSum[j] - util.prefixSum[i])
		else:
			return cost - (l - level) * (freq[j] + util.prefixSum[j] - util.prefixSum[i])
	cost = float('inf')
	for root_idx in range(i, j + 1):
		cost = min(cost, freq[root_idx] * level + util(freq, i, root_idx - 1, level + 1) + util(freq, root_idx + 1, j, level + 1))
	util.mem[i][j] = [level, cost]
	return cost

def prefixSum(arr, n):
	s = [0]
	for i in range(n - 1):
		s.append(s[-1] + arr[i])
	return s

def minCostBST(arr: List[int], freq: List[int]) -> int:
	n = len(arr)
	util.mem = [[None for i in range(n)] for j in range(n)]
	util.prefixSum = prefixSum(freq, n)
	return util(freq, 0, n - 1, 1)

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		return minCostBST(keys, freq)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return self.solve(freq, keys, dp, n, 0, n - 1)

	def solve(self, freqs, keys, dp, n, start, end):
		if start > end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		Freq = 0
		for i in range(start, end + 1):
			Freq += freqs[i]
		MIN = 10 ** 10
		for i in range(start, end + 1):
			left = self.solve(freqs, keys, dp, n, start, i - 1)
			right = self.solve(freqs, keys, dp, n, i + 1, end)
			MIN = min(MIN, left + right)
		cost = MIN + Freq
		dp[start][end] = cost
		return cost


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1 for _ in range(n)] for _ in range(n)]
		return self.solve(keys, freq, dp, 0, n - 1)

	def solve(self, keys, freqs, dp, i, j):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		totalFreqs = 0
		for k in range(i, j + 1):
			totalFreqs += freqs[k]
		MIN = 10 ** 10
		for k in range(i, j + 1):
			left = self.solve(keys, freqs, dp, i, k - 1)
			right = self.solve(keys, freqs, dp, k + 1, j)
			MIN = min(MIN, left + right)
		cost = totalFreqs + MIN
		dp[i][j] = cost
		return cost
		print(totalFreqs)
		return


class Solution:

	def __init__(self):
		self.d = {}

	def s(self, l):
		return sum(l)

	def optimalSearchTree(self, keys, freq, n):

		def optCost(freq, i, j):
			if j < i:
				return 0
			if j == i:
				return freq[i]
			if (i, j) in self.d.keys():
				return self.d[i, j]
			fsum = self.s(freq[i:j + 1])
			Min = 999999999999
			for r in range(i, j + 1):
				cost = optCost(freq, i, r - 1) + optCost(freq, r + 1, j)
				if cost < Min:
					Min = cost
			self.d[i, j] = Min + fsum
			return Min + fsum
		return optCost(freq, 0, n - 1)


class Solution:

	def find_cost(self, arr):
		n = len(arr)
		dp = [[0 for col in range(n)] for row in range(n)]
		for i in range(n):
			for j in range(i, n):
				if i == j:
					dp[i][j] = arr[i]
				else:
					dp[i][j] = dp[i][j - 1] + arr[j]
		return dp

	def helper(self, freq, i, j, cost_arr, mem):
		if i > j:
			return 0
		if i == j:
			return freq[i]
		key = (i, j)
		if key in mem:
			return mem[key]
		min_cost = float('inf')
		for k in range(i, j + 1):
			cost = cost_arr[i][j] + self.helper(freq, i, k - 1, cost_arr, mem) + self.helper(freq, k + 1, j, cost_arr, mem)
			min_cost = min(min_cost, cost)
		mem[key] = min_cost
		return min_cost

	def optimalSearchTree(self, keys, freq, n):
		cost_arr = self.find_cost(freq)
		mem = {}
		return self.helper(freq, 0, n - 1, cost_arr, mem)


from collections import defaultdict

class Solution:

	def util_func(self, keys, freq, left, right, pre_sum, d):
		if d[left, right] != -1:
			return d[left, right]
		if left == right:
			return freq[left]
		if left > right:
			return 0
		ans = float('inf')
		for i in range(left, right + 1):
			ans = min(ans, self.util_func(keys, freq, left, i - 1, pre_sum, d) + self.util_func(keys, freq, i + 1, right, pre_sum, d) + pre_sum[right + 1] - pre_sum[left])
		d[left, right] = ans
		return ans

	def optimalSearchTree(self, keys, freq, n):
		d = defaultdict(lambda : -1)
		pre_sum = [0] * (n + 1)
		for i in range(n):
			pre_sum[i + 1] = pre_sum[i] + freq[i]
		return self.util_func(keys, freq, 0, n - 1, pre_sum, d)


INF = float('inf')

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		N = len(keys)
		dp = [[INF] * (N + 2) for _ in range(N + 2)]
		keys = [0] + keys
		freq = [0] + freq
		for i in range(1, N + 1):
			dp[i][i] = freq[i]
			dp[i][i - 1] = 0
		dp[N + 1][N] = 0
		for r in range(1, N):
			for i in range(1, N - r + 1):
				j = r + i
				freq_sum = 0
				for index in range(i, j + 1):
					freq_sum += freq[index]
				for k in range(i, j + 1):
					dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + freq_sum)
		return dp[1][N]


INT_MAX = 2147483647

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		cost = [[0 for x in range(n)] for y in range(n)]
		for i in range(0, n):
			cost[i][i] = freq[i]
		for length in range(2, n + 1):
			for i in range(0, n - length + 1):
				j = i + length - 1
				if length == 2:
					cost[i][j] = sum(freq[i:j + 1]) + min(cost[i][i], cost[j][j])
				else:
					minCost = INT_MAX
					currCost = 0
					for k in range(i, j + 1):
						if k - 1 >= 0 and k + 1 < n:
							currCost = cost[i][k - 1] + cost[k + 1][j]
						else:
							if k - 1 < 0:
								currCost = cost[k + 1][j]
							if k + 1 >= n:
								currCost = cost[i][k - 1]
						minCost = min(minCost, currCost)
					cost[i][j] = sum(freq[i:j + 1]) + minCost
		return cost[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[-1] * (n + 1) for i in range(n + 1)]

		def solve(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == j:
				dp[i][j] = freq[i]
			else:
				res = float('inf')
				for k in range(i, j + 1):
					l = solve(i, k - 1)
					r = solve(k + 1, j)
					res = min(res, sum(freq[i:j + 1]) + l + r)
				dp[i][j] = res
			return dp[i][j]
		return solve(0, len(keys) - 1)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		d = [[0 for i in range(n)] for j in range(n)]
		for i in range(0, n):
			d[i][i] = freq[i]
		for l in range(2, n + 1):
			for i in range(n - l + 2):
				j = l + i - 1
				if i >= n or j >= n:
					break
				d[i][j] = float('inf')
				for k in range(i, j + 1):
					v = 0
					if k > i:
						v += d[i][k - 1]
					if k < j:
						v += d[k + 1][j]
					v += sum(freq[i:j + 1])
					d[i][j] = min(d[i][j], v)
		return d[0][n - 1]


class Solution:

	def compute_cost(self, arr):
		n = len(arr)
		result = [[0 for col in range(n)] for row in range(n)]
		for row in range(n):
			for col in range(row, n):
				if row == col:
					result[row][col] = arr[col]
				else:
					result[row][col] = arr[col] + result[row][col - 1]
		return result

	def helper(self, arr, i, j, cost, mem):
		if i > j:
			return 0
		if mem[i][j] != -1:
			return mem[i][j]
		ans = float('inf')
		for k in range(i, j + 1):
			temp_ans = cost[i][j] + self.helper(arr, i, k - 1, cost, mem) + self.helper(arr, k + 1, j, cost, mem)
			ans = min(ans, temp_ans)
		mem[i][j] = ans
		return ans

	def optimalSearchTree(self, keys, freq, n):
		cost = self.compute_cost(freq)
		mem = [[-1 for col in range(n + 1)] for row in range(n + 1)]
		return self.helper(freq, 0, n - 1, cost, mem)


class Solution:

	def optimalSearchTree(self, A, F, n):
		dp = [[-1] * (1 + n) for i in range(n + 1)]

		def find(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if j == i:
				dp[i][j] = F[i]
			else:
				ans = float('inf')
				for k in range(i, j + 1):
					left = find(i, k - 1)
					right = find(k + 1, j)
					ans = min(ans, sum(F[i:j + 1]) + left + right)
				dp[i][j] = ans
			return dp[i][j]
		return find(0, len(A) - 1)


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for j in range(n)] for i in range(n)]
		psa = [0] * n
		psa[0] = freq[0]
		for i in range(1, n):
			psa[i] = psa[i - 1] + freq[i]
		for g in range(n):
			i = 0
			j = g
			while j < len(dp):
				if g == 0:
					dp[i][j] = freq[i]
				elif g == 1:
					f1 = freq[i]
					f2 = freq[j]
					dp[i][j] = min(f1 + 2 * f2, 2 * f1 + f2)
				else:
					mini = float('inf')
					if i == 0:
						val = 0
					else:
						val = psa[i - 1]
					fs = psa[j] - val
					for k in range(i, j + 1):
						if k == i:
							left = 0
						else:
							left = dp[i][k - 1]
						if k == j:
							right = 0
						else:
							right = dp[k + 1][j]
						if left + right + fs < mini:
							mini = left + right + fs
					dp[i][j] = mini
				i += 1
				j += 1
		return dp[0][n - 1]


INT_MAX = 1000000

def sum1(freq, i, j):
	s = 0
	for k in range(i, j + 1):
		s += freq[k]
	return s

class Solution:

	def optimalSearchTree(self, keys, freq, n):
		cost = [[INT_MAX for x in range(n)] for y in range(n)]
		for g in range(0, n):
			i = 0
			for j in range(g, n):
				if g == 0:
					cost[i][j] = freq[i]
				elif g == 1:
					cost[i][j] = min(freq[i] + 2 * freq[j], 2 * freq[i] + freq[j])
				else:
					min1 = INT_MAX
					sum2 = sum1(freq, i, j)
					for k in range(i, j + 1):
						left = 0
						if k > i:
							left = cost[i][k - 1]
						right = 0
						if k < j:
							right = cost[k + 1][j]
						if left + right + sum2 < min1:
							min1 = left + right + sum2
					cost[i][j] = min1
				i += 1
		return cost[0][n - 1]


class Solution:

	def optimalSearchTree(self, keys, freq, n):
		dp = [[0 for _ in keys] for _ in keys]
		for g in range(n):
			for (i, j) in zip(range(n - g), range(g, n)):
				mini = -1
				sumi = 0
				for k in range(i, j + 1):
					sumi += freq[k]
				for k in range(i, j + 1):
					left = dp[i][k - 1] if k > i else 0
					right = dp[k + 1][j] if k < j else 0
					z = left + right + sumi
					mini = z if mini < 0 else min(mini, z)
				dp[i][j] = mini
		return dp[0][n - 1]


class Solution:

	def compute(self, arr, start, end):
		ans = 0
		while start < end:
			ans += arr[start]
			ans += arr[end]
			start += 1
			end -= 1
		if start == end:
			ans += arr[start]
		return ans

	def optimal_helper(self, keys, freq, left, right, mem):
		if left > right:
			return 0
		if left == right:
			return freq[left]
		if mem[left][right] != -1:
			return mem[left][right]
		intermediate_cost = self.compute(freq, left, right)
		min_cost = float('inf')
		for curr in range(left, right + 1):
			curr_cost = intermediate_cost + self.optimal_helper(keys, freq, left, curr - 1, mem) + self.optimal_helper(keys, freq, curr + 1, right, mem)
			min_cost = min(min_cost, curr_cost)
		mem[left][right] = min_cost
		return min_cost

	def optimalSearchTree(self, keys, freq, n):
		mem = [[-1 for i in range(n)] for j in range(n)]
		return self.optimal_helper(keys, freq, 0, n - 1, mem)