$(10\%)$ Suppose that we are given a sequence of $n$ matrices $A_1,A_2,$dots,$A_n,$ where matrix $A_i$ has

dimension $d_{i-1}{d}_i$ for each $1in.$ In the standard matrix multiplication algorithm, the

product of two matrices, say $A_1*A_2,$ requires $d_0{d}_1{d}_2$ scalar multiplications. Moreover,

the matrix multiplication is associative. For example, $A_1*(A_2*A_3)=(A_1*A_2)*A_3($i$.$e$.,$ these

two different parenthesizations yield the same product$).$ However, different parenthesizations

for a product of matrices may have different scalar multiplications. For example, $A_1*(A_2*A_3)$

has $d_1{d}_2{d}_3+d_0{d}_1{d}_3$ scalar multiplications, but $(A_1*A_2)*A_3$ has $d_0{d}_1{d}_2+$

$d_0{d}_2{d}_3$ scalar multiplications. A product of matrices is fully parenthesized if it is either a

single matrix or the product of two fully parenthesized matrix products. Please design a

dynamic programming algorithm to fully parenthesize the product $A_1*A_2*dots*A_n$ in a way that

minimizes the total number of scalar multiplications $(3\%).$ What is the recursive formula for

your dynamic programming algorithm $(3\%)?$ Note that you have to justify the correctness of

your recursive formula. Also analyze the time complexity of your dynamic programming

algorithm $(4\%).$