Given an array p[] of length n used to denote the dimensions of a series of matrices such that dimension of i'th matrix is p[i] * p[i+1]. There are a total of n-1 matrices. Find the most efficient way to multiply these matrices together. 
The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications such that you need to perform minimum number of multiplications. There are many options to multiply a chain of matrices because matrix multiplication is associative i.e. no matter how one parenthesize the product, the result will be the same.
Example 1:
Input: 
n = 5
p[] = {1, 2, 3, 4, 5}
Output: (((AB)C)D)
Explaination: The total number of 
multiplications are (1*2*3) + (1*3*4) 
+ (1*4*5) = 6 + 12 + 20 = 38.
 
Example 2:
Input: 
n = 3
p = {3, 3, 3}
Output: (AB)
Explaination: The total number of 
multiplications are (3*3*3) = 27.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function matrixChainOrder() which takes n and p[] as input parameters and returns the string with the proper order of parenthesis for n-1 matrices. Use uppercase alphabets to denote each matrix.
Expected Time Complexity: O(n^{3})
Expected Auxiliary Space: O(n^{2})
Constraints:
2 ≤ n ≤ 26 
1 ≤ p[i] ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def matrixChainOrder(self, p, n):

        # code here

Solutions:
import sys

class Solution:

	def __init__(self):
		self.char = 'A'
		self.cnt = 0
		self.string = ''

	def showBrackets(self, i, j, brackets):
		if i == j:
			if self.cnt != 0:
				self.string += ord(self.char) + self.cnt
			else:
				self.string += self.char
			if self.char == 'Z':
				self.char = 'A'
				self.cnt += 1
			else:
				self.char = chr(ord(self.char) + 1)
		else:
			self.string += '('
			self.showBrackets(i, brackets[i][j], brackets)
			self.showBrackets(brackets[i][j] + 1, j, brackets)
			self.string += ')'
		return self.string

	def matrixChainOrder(self, p, n):
		n -= 1
		ans = [[0] * n for i in range(n)]
		brackets = [[0] * n for i in range(n)]
		(size, j) = (1, 0)
		cost = 0
		while size < n:
			i = 0
			while i < n - size:
				j = i + size
				ans[i][j] = sys.maxsize
				k = i
				while k < j:
					cost = ans[i][k] + ans[k + 1][j] + p[i] * p[j + 1] * p[k + 1]
					if cost < ans[i][j]:
						ans[i][j] = cost
						brackets[i][j] = k
					k += 1
				i += 1
			size += 1
		return self.showBrackets(0, n - 1, brackets)


class Solution:

	def matrixChainOrder(self, p, n):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		ind = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n - 1, 0, -1):
			for j in range(i + 1, n):
				mini = 1000000000.0
				it = -1
				for k in range(i, j):
					x = p[i - 1] * p[k] * p[j] + dp[i][k] + dp[k + 1][j]
					if x < mini:
						mini = x
						it = k
				dp[i][j] = mini
				ind[i][j] = it
		self.res = ''
		self.name = 'A'
		self.count = 0

		def showBrackets(i, j):
			if i == j:
				if self.count != 0:
					self.res += chr(ord(self.name) + self.count)
				else:
					self.res += self.name
				if self.name == 'Z':
					self.name = 'A'
				else:
					self.name = chr(ord(self.name) + 1)
			else:
				self.res += '('
				showBrackets(i, ind[i][j])
				showBrackets(ind[i][j] + 1, j)
				self.res += ')'
		showBrackets(1, n - 1)
		return self.res


from math import inf

class Solution:

	def matrixChainOrder(self, x, n):
		if n == 2:
			return 'A'
		dp = {}

		def f(i, j):
			if j - i <= 1:
				return (0, chr(i + 65))
			if (i, j) in dp:
				return dp[i, j]
			ans = (inf, '')
			for k in range(i + 1, j):
				(l, ls) = f(i, k)
				(r, rs) = f(k, j)
				ans = min(ans, (l + r + x[i] * x[j] * x[k], '(' + ls + chr(k + 65) + rs + ')'))
			dp[i, j] = ans
			return ans
		a = f(0, n - 1)[1]
		res = ''
		l = len(a)
		for i in range(l - 1):
			if a[i + 1] in '()' and a[i] not in '()':
				continue
			else:
				res += a[i]
		return res + a[-1]


class Solution:

	def matrixChainOrder(self, p, n):
		global dp, d
		dp = [[[-1, ''] for _ in range(n)] for __ in range(n)]
		alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
		d = {}
		for i in range(26):
			d[i + 1] = alp[i]

		def recur(p, i, j):
			global dp, d
			if i > j:
				return [0, '']
			if i == j:
				return [0, d[i]]
			if dp[i][j][0] != -1:
				return dp[i][j]
			fin = 10 ** 9
			fint = ''
			for k in range(i, j):
				ans = p[i - 1] * p[k] * p[j] + recur(p, i, k)[0] + recur(p, k + 1, j)[0]
				temp = '(' + recur(p, i, k)[1] + recur(p, k + 1, j)[1] + ')'
				if ans < fin:
					fin = ans
					fint = temp
			dp[i][j] = [fin, fint]
			return [fin, fint]
		return recur(p, 1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def fun(i, j):
			if i == j:
				s = ''
				ch = chr(64 + i)
				s = s + ch
				return [0, s]
			key = str(i) + '$' + str(j)
			if dp.get(key) != None:
				return dp[key]
			mini = 1e+20
			s = ''
			for k in range(i, j):
				left = fun(i, k)
				right = fun(k + 1, j)
				curr_operations = left[0] + right[0] + p[i - 1] * p[k] * p[j]
				if curr_operations < mini:
					mini = curr_operations
					s = '(' + left[1] + right[1] + ')'
			dp[key] = [mini, s]
			return dp[key]
		return fun(1, n - 1)[1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = input().split()
		for i in range(n):
			p[i] = int(p[i])
		ob = Solution()
		print(ob.matrixChainOrder(p, n))


class Solution:

	def matrixChainOrder(self, p, n):
		dp = [[0 for i in range(n)] for i in range(n)]
		brkt = [[0 for i in range(n)] for i in range(n)]
		for l in range(2, n):
			for i in range(1, n - l + 1):
				j = i + l - 1
				dp[i][j] = float('inf')
				for k in range(i, j):
					q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
					if q < dp[i][j]:
						dp[i][j] = q
						brkt[i][j] = k

		def calc(i, j):
			if i == j:
				return str(chr(i - 1 + ord('A')))
			if i + 1 == j:
				s = '(' + str(chr(i - 1 + ord('A'))) + str(chr(j - 1 + ord('A'))) + ')'
				return s
			k = brkt[i][j]
			s = '(' + calc(i, k) + calc(k + 1, j) + ')'
			return s
		return calc(1, n - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = input().split()
		for i in range(n):
			p[i] = int(p[i])
		ob = Solution()
		print(ob.matrixChainOrder(p, n))


class Solution:

	def matrixChainOrder(self, p, n):
		dp = [[0 for i in range(n - 1)] for j in range(n - 1)]
		d = {i: chr(i + 65) for i in range(26)}
		m = len(dp)
		for g in range(m):
			i = 0
			j = i + g
			while j < m:
				if g == 0:
					dp[i][j] = [d[i], 0]
				elif g == 1:
					dp[i][j] = ['(' + d[i] + d[j] + ')', p[i] * p[j] * p[j + 1]]
				else:
					ma = float('inf')
					s = ''
					for k in range(i, j):
						res = dp[i][k][1] + dp[k + 1][j][1] + p[i] * p[k + 1] * p[j + 1]
						if res < ma:
							ma = res
							s = '(' + dp[i][k][0] + dp[k + 1][j][0] + ')'
					dp[i][j] = [s, ma]
				i += 1
				j += 1
		return dp[0][-1][0]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = input().split()
		for i in range(n):
			p[i] = int(p[i])
		ob = Solution()
		print(ob.matrixChainOrder(p, n))


import sys

class Solution:

	def __init__(self):
		self.char = 'A'
		self.cnt = 0
		self.string = ''

	def showBrackets(self, i, j, brackets):
		if i == j:
			if self.cnt != 0:
				self.string += ord(self.char) + self.cnt
			else:
				self.string += self.char
			if self.char == 'Z':
				self.char = 'A'
				self.cnt += 1
			else:
				self.char = chr(ord(self.char) + 1)
		else:
			self.string += '('
			self.showBrackets(i, brackets[i][j], brackets)
			self.showBrackets(brackets[i][j] + 1, j, brackets)
			self.string += ')'
		return self.string

	def matrixChainOrder(self, p, n):
		n -= 1
		ans = [[0] * n for i in range(n)]
		brackets = [[0] * n for i in range(n)]
		(size, j) = (1, 0)
		cost = 0
		while size < n:
			i = 0
			while i < n - size:
				j = i + size
				ans[i][j] = sys.maxsize
				k = i
				while k < j:
					cost = ans[i][k] + ans[k + 1][j] + p[i] * p[j + 1] * p[k + 1]
					if cost < ans[i][j]:
						ans[i][j] = cost
						brackets[i][j] = k
					k += 1
				i += 1
			size += 1
		return self.showBrackets(0, n - 1, brackets)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = input().split()
		for i in range(n):
			p[i] = int(p[i])
		ob = Solution()
		print(ob.matrixChainOrder(p, n))


class Solution:

	def brack(self, ans, posi, i, j):
		if j == i:
			ans.append(chr(65 + i))
			return
		ans.append('(')
		self.brack(ans, posi, i, posi[i][j])
		self.brack(ans, posi, posi[i][j] + 1, j)
		ans.append(')')

	def matrixChainOrder(self, p, n):
		dp = [[0 for _ in range(n - 1)] for _ in range(n - 1)]
		posi = [[0 for _ in range(n - 1)] for _ in range(n - 1)]
		for L in range(1, n):
			for i in range(n - L - 1):
				c = float('inf')
				pos = None
				for k in range(i, i + L):
					if c > dp[i][k] + p[i] * p[i + L + 1] * p[k + 1] + dp[k + 1][i + L]:
						c = dp[i][k] + p[i] * p[i + L + 1] * p[k + 1] + dp[k + 1][i + L]
						pos = k
				dp[i][i + L] = c
				posi[i][i + L] = pos
		ans = []
		self.brack(ans, posi, 0, n - 2)
		return ''.join(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = input().split()
		for i in range(n):
			p[i] = int(p[i])
		ob = Solution()
		print(ob.matrixChainOrder(p, n))


class Solution:

	def matrixChainOrder(self, p, n):
		dp = [[0 for i in range(n)] for i in range(n)]
		brkt = [[0 for i in range(n)] for i in range(n)]
		for l in range(2, n):
			for i in range(1, n - l + 1):
				j = i + l - 1
				dp[i][j] = float('inf')
				for k in range(i, j):
					q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
					if q < dp[i][j]:
						dp[i][j] = q
						brkt[i][j] = k

		def calc(i, j):
			if i == j:
				return str(chr(i - 1 + ord('A')))
			if i + 1 == j:
				s = '(' + str(chr(i - 1 + ord('A'))) + str(chr(j - 1 + ord('A'))) + ')'
				return s
			k = brkt[i][j]
			s = '(' + calc(i, k) + calc(k + 1, j) + ')'
			return s
		return calc(1, n - 1)


class Solution:

	def matrixChainOrder(self, p, n):
		d = {}
		t = [[['', -1]] * (n + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			d[i] = chr(ord('@') + i)

		def rec(i, j):
			if i == j:
				return [d.get(i, ''), 0]
			ans = float('inf')
			s = ''
			if t[i][j][1] != -1:
				return t[i][j]
			for k in range(i, j):
				left = rec(i, k)
				right = rec(k + 1, j)
				temp = left[1] + right[1] + p[i - 1] * p[k] * p[j]
				if ans > temp:
					ans = temp
					s = '(' + left[0] + right[0] + ')'
			t[i][j] = [s, ans]
			return t[i][j]
		return rec(1, n - 1)[0]


import sys

class Solution:

	def __init__(self):
		self.char = 'A'
		self.res = list()

	def toMatrixChain(self, i, j, s):
		if i == j:
			self.res.append(self.char)
			self.char = chr(ord(self.char) + 1)
			return
		self.res.append('(')
		x = s[i][j]
		self.toMatrixChain(i, x, s)
		self.toMatrixChain(x + 1, j, s)
		self.res.append(')')

	def matrixChainOrder(self, arr, n):
		dp = [[0 for i in range(n - 1)] for i in range(n - 1)]
		s = [[0 for i in range(n - 1)] for i in range(n - 1)]
		res = []
		for gap in range(n - 1):
			i = 0
			j = gap
			while j < n - 1:
				if gap == 0:
					dp[i][j] = 0
				elif gap == 1:
					dp[i][j] = arr[i] * arr[j] * arr[j + 1]
					s[i][j] = i
				else:
					m = 100000000000
					for k in range(i, j):
						x = dp[i][k] + dp[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1]
						if x < m:
							m = x
							s[i][j] = k
					dp[i][j] = m
				i += 1
				j += 1
		self.toMatrixChain(0, n - 2, s)
		res = ''
		for i in self.res:
			res += i
		return res


class Solution:

	def brack(self, ans, posi, i, j):
		if j == i:
			ans.append(chr(65 + i))
			return
		ans.append('(')
		self.brack(ans, posi, i, posi[i][j])
		self.brack(ans, posi, posi[i][j] + 1, j)
		ans.append(')')

	def matrixChainOrder(self, p, n):
		dp = [[0 for _ in range(n - 1)] for _ in range(n - 1)]
		posi = [[0 for _ in range(n - 1)] for _ in range(n - 1)]
		for L in range(1, n):
			for i in range(n - L - 1):
				c = float('inf')
				pos = None
				for k in range(i, i + L):
					if c > dp[i][k] + p[i] * p[i + L + 1] * p[k + 1] + dp[k + 1][i + L]:
						c = dp[i][k] + p[i] * p[i + L + 1] * p[k + 1] + dp[k + 1][i + L]
						pos = k
				dp[i][i + L] = c
				posi[i][i + L] = pos
		ans = []
		self.brack(ans, posi, 0, n - 2)
		return ''.join(ans)


class Solution:

	def matrixChainOrder(self, l, n):
		dp = [[['', -1] for _ in range(n)] for _ in range(n)]

		def ss(i, j):
			if i == j:
				return [chr(65 + i - 1), 0]
			if dp[i][j][1] != -1:
				return dp[i][j]
			ans = float('inf')
			s = ''
			for k in range(i, j):
				lft = ss(i, k)
				rgt = ss(k + 1, j)
				t = lft[1] + rgt[1] + l[k] * l[i - 1] * l[j]
				s1 = '(' + lft[0] + rgt[0] + ')'
				if t < ans:
					ans = t
					s = s1
			dp[i][j] = [s, ans]
			return dp[i][j]
		return ss(1, n - 1)[0]


class Solution:

	def matrixChainOrder(self, arr, N):
		import sys
		p = arr
		global b
		m = [[0 for x in range(N)] for x in range(N)]
		b = [[0 for x in range(N)] for x in range(N)]
		for i in range(1, N):
			m[i][i] = 0
		for L in range(2, N):
			for i in range(1, N - L + 1):
				j = i + L - 1
				m[i][j] = sys.maxsize
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
					if q < m[i][j]:
						m[i][j] = q
						b[i][j] = k
		(name, s) = self.printpar(b, 1, N - 1, 65)
		return s

	def printpar(self, b, i, j, name, s=''):
		if i == j:
			s += chr(name)
			name += 1
			return (name, s)
		s += '('
		(name, s) = self.printpar(b, i, b[i][j], name, s)
		(name, s) = self.printpar(b, b[i][j] + 1, j, name, s)
		s += ')'
		return (name, s)


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def helper(i, j):
			if i == j:
				s = ''
				c = chr(64 + i)
				s = s + c
				return [0, s]
			key = str(i) + '$' + str(j)
			if dp.get(key) != None:
				return dp[key]
			mii = 1e+20
			s = ''
			for k in range(i, j):
				l = helper(i, k)
				r = helper(k + 1, j)
				co = l[0] + r[0] + p[i - 1] * p[k] * p[j]
				if co < mii:
					mii = co
					s = '(' + l[1] + r[1] + ')'
			dp[key] = [mii, s]
			return dp[key]
		return helper(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		dp = [[0 for i in range(n)] for j in range(n)]
		sp = [['' for i in range(n)] for j in range(n)]
		for gap in range(n - 1):
			i = 0
			j = gap
			while j < n - 1:
				if gap == 0:
					dp[i][j] = 0
					sp[i][j] = ''
					sp[i][j] = chr(ord('A') + i)
				elif gap == 1:
					dp[i][j] = p[i] * p[j] * p[j + 1]
					sp[i][j] = '(' + chr(ord('A') + i) + chr(ord('A') + j) + ')'
				else:
					mini = float('inf')
					for k in range(i, j):
						sm = dp[i][k]
						lm = dp[k + 1][j]
						md = p[i] * p[k + 1] * p[j + 1]
						com = sm + lm + md
						if com < mini:
							mini = com
							dp[i][j] = mini
							sp[i][j] = '(' + sp[i][k] + sp[k + 1][j] + ')'
				j += 1
				i += 1
		return sp[0][n - 2]


import sys

class Solution:

	def __init__(self):
		self.st = ''

	def matrixChainOrder(self, p, n):
		m = [[0 for i in range(n + 1)] for i in range(n + 1)]
		for l in range(2, n):
			for i in range(n - l):
				j = i + l - 1
				m[i][j] = float('Inf')
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
					if q < m[i][j]:
						m[i][j] = q
						m[j][i] = k + 1
		self.printParenthesis(m, n - 2, 0)
		return self.st

	def printParenthesis(self, m, j, i):
		if j == i:
			self.st = self.st + chr(65 + j)
			return
		else:
			self.st = self.st + '('
			self.printParenthesis(m, m[j][i] - 1, i)
			self.printParenthesis(m, j, m[j][i])
			self.st = self.st + ')'


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def solve(arr, i, j):
			if i == j:
				s = ''
				ch = chr(64 + i)
				s = s + ch
				return [0, s]
			key = str(i) + str(j)
			if dp.get(key) != None:
				return dp[key]
			mn = float('inf')
			s = ''
			for k in range(i, j):
				a = solve(p, i, k)
				b = solve(p, k + 1, j)
				temp_ans = a[0] + b[0] + arr[i - 1] * arr[k] * arr[j]
				if temp_ans < mn:
					mn = temp_ans
					s = '(' + a[1] + b[1] + ')'
			dp[key] = [mn, s]
			return dp[key]
		ans = solve(p, 1, n - 1)[1]
		return ans


INV = 10 ** 9 + 7

class Solution:

	def matrixChainOrder(self, p, n):
		if n == 2:
			return 'A'
		dp = [[0] * (n - 1) for _ in range(n + 1)]
		cut = [[-1] * (n - 1) for _ in range(n + 1)]
		for L in range(3, n + 1):
			for si in range(n - L + 1):
				(minval, cp) = (INV, INV)
				for mi in range(si + 1, si + L - 1):
					mv = p[si] * p[mi] * p[si + L - 1] + dp[mi - si + 1][si] + dp[si + L - mi][mi]
					if mv < minval:
						(minval, cp) = (mv, mi)
				dp[L][si] = minval
				cut[L][si] = cp

		def _trace(L, si):
			if L == 3:
				return '({}{})'.format(chr(65 + si), chr(66 + si))
			v = cut[L][si]
			if v == si + 1:
				return '({}{})'.format(chr(65 + si), _trace(L - 1, si + 1))
			elif v == si + L - 2:
				return '({}{})'.format(_trace(L - 1, si), chr(65 + v))
			else:
				return '({}{})'.format(_trace(v - si + 1, si), _trace(si + L - v, v))
		return _trace(n, 0)


INV = 10 ** 9 + 7

class Solution:

	def matrixChainOrder(self, p, n):
		if n == 2:
			return 'A'
		d = [[0] * (n - 1) for i in range(n + 1)]
		c = [[-1] * (n - 1) for i in range(n + 1)]
		for l in range(3, n + 1):
			for si in range(n - l + 1):
				(minval, cp) = (INV, INV)
				for mi in range(si + 1, si + l - 1):
					mv = p[si] * p[mi] * p[si + l - 1] + d[mi - si + 1][si] + d[si + l - mi][mi]
					if mv < minval:
						(minval, cp) = (mv, mi)
				d[l][si] = minval
				c[l][si] = cp

		def foo(l, si):
			if l == 3:
				return '({}{})'.format(chr(65 + si), chr(66 + si))
			v = c[l][si]
			if v == si + 1:
				return '({}{})'.format(chr(65 + si), foo(l - 1, si + 1))
			elif v == si + l - 2:
				return '({}{})'.format(foo(l - 1, si), chr(65 + v))
			else:
				return '({}{})'.format(foo(v - si + 1, si), foo(si + l - v, v))
		return foo(n, 0)


class Solution:

	def printParenthesis(self, m, j, i):
		if j == i:
			print(chr(65 + j), end='')
			return
		else:
			print('(', end='')
			self.printParenthesis(m, m[j][i] - 1, i)
			self.printParenthesis(m, j, m[j][i])
			print(')', end='')

	def matrixChainOrder(self, p, x):
		n = x - 1
		m = [[0 for i in range(n)] for i in range(n)]
		for l in range(2, n + 1):
			for i in range(n - l + 1):
				j = i + l - 1
				m[i][j] = float('Inf')
				for k in range(i, j):
					q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
					if q < m[i][j]:
						m[i][j] = q
						m[j][i] = k + 1
		self.printParenthesis(m, n - 1, 0)
		return ''


from functools import lru_cache

class Solution:

	def matrixChainOrder(self, p, n):
		if n == 2:
			return 'A'

		@lru_cache(None)
		def rec(l, r):
			if l == r:
				return [0, chr(l + 64)]
			m = float('inf')
			res = ''
			for i in range(l, r):
				(lc, lv) = rec(l, i)
				(rc, rv) = rec(i + 1, r)
				t = lc + rc + p[l - 1] * p[i] * p[r]
				if t < m:
					m = t
					res = '(' + lv + rv + ')'
			return [m, res]
		return rec(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		from math import inf
		dp = [[0 for _ in range(n)] for _ in range(n)]
		brkt = [[0 for _ in range(n)] for _ in range(n)]
		for l in range(2, n):
			for i in range(1, n - l + 1):
				j = i + l - 1
				dp[i][j] = inf
				for k in range(i, j):
					q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
					if q < dp[i][j]:
						dp[i][j] = q
						brkt[i][j] = k

		def helper(i, j):
			if i == j:
				return chr(64 + i)
			if i + 1 == j:
				s = '(' + chr(64 + i) + chr(64 + j) + ')'
				return s
			k = brkt[i][j]
			s = '(' + helper(i, k) + helper(k + 1, j) + ')'
			return s
		return helper(1, n - 1)


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def fun(i, j):
			if i == j:
				s = ''
				ch = chr(64 + i)
				s = s + ch
				return [0, s]
			key = str(i) + '$' + str(j)
			if dp.get(key) != None:
				return dp[key]
			mini = 1e+20
			s = ''
			for k in range(i, j):
				left = fun(i, k)
				right = fun(k + 1, j)
				curr_operations = left[0] + right[0] + p[i - 1] * p[k] * p[j]
				if curr_operations < mini:
					mini = curr_operations
					s = '(' + left[1] + right[1] + ')'
			dp[key] = [mini, s]
			return dp[key]
		return fun(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def recur(i, j):
			if i == j:
				return [0, chr(64 + i)]
			key = str(i) + '@' + str(j)
			if dp.get(key) != None:
				return dp[key]
			vmin = 1e+19
			s = ''
			for k in range(i, j):
				l = recur(i, k)
				r = recur(k + 1, j)
				curr_op = l[0] + r[0] + p[i - 1] * p[k] * p[j]
				if curr_op < vmin:
					vmin = curr_op
					s = '(' + l[1] + r[1] + ')'
			dp[key] = [vmin, s]
			return dp[key]
		return recur(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		dp = {}

		def helper(i, j):
			if i == j:
				ch = chr(64 + i)
				return (0, ch)
			if (i, j) in dp:
				return dp[i, j]
			s = ''
			m = 1e+20
			for k in range(i, j):
				left = helper(i, k)
				right = helper(k + 1, j)
				cost = left[0] + right[0] + p[i - 1] * p[k] * p[j]
				if cost < m:
					m = cost
					s = '(' + str(left[1]) + str(right[1]) + ')'
			dp[i, j] = (m, s)
			return dp[i, j]
		return helper(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, p, n):
		self.ans = ''

		def print_optimal_parens(s, i, j):
			if i == j:
				self.ans += chr(i + 64)
			else:
				self.ans += '('
				print_optimal_parens(s, i, s[i][j])
				print_optimal_parens(s, s[i][j] + 1, j)
				self.ans += ')'

		def mcm(n, p):
			f = float('inf')
			m = [[-1 for i in range(n + 1)] for j in range(n + 1)]
			s = [[-1 for p in range(n + 1)] for w in range(n + 1)]
			for i in range(n + 1):
				m[i][i] = 0
			for l in range(2, n + 1):
				for i in range(1, n - l + 2):
					j = i + l - 1
					m[i][j] = f
					for k in range(i, j):
						q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
						if q < m[i][j]:
							m[i][j] = q
							s[i][j] = k
			print_optimal_parens(s, 1, n)
		mcm(n - 1, p)
		return self.ans


class Solution:

	def solve(self, i, j):
		if i >= j:
			return (0, chr(64 + i))
		if self.dp[i][j] != None:
			return self.dp[i][j]
		ans = (float('inf'), '')
		for k in range(i, j):
			l = self.solve(i, k)
			r = self.solve(k + 1, j)
			if ans[0] > l[0] + r[0] + self.p[i - 1] * self.p[k] * self.p[j]:
				ans = (l[0] + r[0] + self.p[i - 1] * self.p[k] * self.p[j], '(' + l[1] + r[1] + ')')
		self.dp[i][j] = ans
		return ans

	def matrixChainOrder(self, p, n):
		self.ansorder = []
		self.p = p
		self.dp = [[None for j in range(n + 1)] for i in range(n + 1)]
		return self.solve(1, n - 1)[1]


class Solution:

	def matrixChainOrder(self, l, n):
		dp = [[[0, ''] for i in range(n)] for j in range(n)]
		for i in range(1, n):
			(a, b) = (0, i)
			for j in range(n - i):
				if i == 1:
					dp[a][b][1] = str(chr(ord('A') + j))
				else:
					dp[a][b][0] = float('inf')
					x = a
					for k in range(a + 1, b):
						t = dp[a][k][0] + dp[k][b][0] + l[a] * l[k] * l[b]
						if dp[a][b][0] > t:
							dp[a][b][0] = dp[a][k][0] + dp[k][b][0] + l[a] * l[k] * l[b]
							x = k
					dp[a][b][1] = '(' + dp[a][x][1] + dp[x][b][1] + ')'
				a += 1
				b += 1
		return dp[0][n - 1][1]


class Solution:

	def matrixChainOrder(self, p, n):
		res = ''
		memo = {}
		if n == 2:
			return 'A'

		def dp(i, j):
			if i > j:
				return
			if i == j:
				return (0, chr(64 + i))
			if abs(j - i) == 1:
				return (p[i - 1] * p[i] * p[j], chr(64 + i) + chr(64 + j))
			if (i, j) in memo:
				return memo[i, j]
			m = float('inf')
			res = ''
			for a in range(i, j):
				(count2, s2) = dp(i, a)
				(count, s) = dp(a + 1, j)
				q = count + count2 + p[i - 1] * p[a] * p[j]
				if q < m:
					m = q
					res = ''
					if a == i:
						res = s2 + '(' + s + ')'
					elif a == j - 1:
						res = '(' + s2 + ')' + s
					else:
						res = '(' + s2 + ')' + '(' + s + ')'
			memo[i, j] = (m, res)
			return (m, res)
		(c, ans) = dp(1, n - 1)
		return '(' + ans + ')'


from functools import lru_cache
import sys
sys.setrecursionlimit(100000)

class Solution:

	def matrixChainOrder(self, p, n):

		@lru_cache(None)
		def util(start_index, end_index):
			if start_index > end_index:
				return ('', float('inf'))
			if start_index == end_index:
				return (chr(start_index + ord('A')), 0)
			min_cost = float('inf')
			min_string = ''
			for index in range(start_index + 1, end_index + 1):
				(comb1, cost1) = util(start_index, index - 1)
				(comb2, cost2) = util(index, end_index)
				final_cost = cost1 + cost2 + p[start_index] * p[index] * p[end_index + 1]
				if final_cost < min_cost:
					min_string = '(' + comb1 + comb2 + ')'
					min_cost = final_cost
			return (min_string, min_cost)
		(comn, _) = util(0, n - 2)
		return comn


MOD = pow(10, 9) + 7

class Solution:

	def matrixChainOrder(self, p, n):
		if n == 2:
			return 'A'
		dp = [[0] * (n - 1) for i in range(n + 1)]
		c = [[-1] * (n - 1) for i in range(n + 1)]
		for i in range(3, n + 1):
			for j in range(n - i + 1):
				(minval, cp) = (MOD, MOD)
				for k in range(j + 1, j + i - 1):
					mv = p[j] * p[k] * p[j + i - 1] + dp[k - j + 1][j] + dp[j + i - k][k]
					if mv < minval:
						(minval, cp) = (mv, k)
				dp[i][j] = minval
				c[i][j] = cp

		def T(i, j):
			if i == 3:
				return '({}{})'.format(chr(65 + j), chr(66 + j))
			v = c[i][j]
			if v == j + 1:
				return '({}{})'.format(chr(65 + j), T(i - 1, 1 + j))
			elif v == j + i - 2:
				return '({}{})'.format(T(i - 1, j), chr(65 + v))
			else:
				return '({}{})'.format(T(v - j + 1, j), T(j + i - v, v))
		return T(n, 0)