# Exercise 15.2.1

Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is $\langle 5, 10, 3, 12, 5, 50, 6 \rangle$.

### Python runner output

((AA₁)((A₂A₃)(A₄A₅)))


### Python code

import sys

sizes = [30, 35, 15, 5, 10, 20, 25]

def subscript(n):
chars = "₀₁₂₃₄₅₆₇₈₉"
result = []
while n:
rem = n % 10
n //= 10
result.append(chars[rem])

return ''.join(reversed(result))

def order(dimensions):
n = len(dimensions) - 1
memo = [[-1] * n for _ in range(n)]
choices = [[-1] * n for _ in range(n)]
for i in range(0, n):
memo[i][i] = 0

for length in range(1, n):
for start in range(0, n - length):
end = start + length
cheapest = sys.maxsize
for split in range(start, end):
cost = memo[start][split] + memo[split + 1][end] + \
dimensions[start] * dimensions[split + 1] * \
dimensions[end + 1]

if cost < cheapest:
cheapest = cost
memo[start][end] = cost
choices[start][end] = split

def optimal(i, j):
if i == j:
return "A" + subscript(i)
else:
left = optimal(i, choices[i][j])
right = optimal(choices[i][j] + 1, j)
return f"({left}{right})"

return (memo[n - 1], optimal(0, n - 1))