ou are given a sequence of matrices A$0,$ A$1,...,$ A i $,...,$ A n where each matrix A i has

dimensions p i$1$ p i $.$ Your task is to determine the minimum number of scalar multiplications

needed to multiply the entire sequence of matrices using a divide$-$and$-$conquer approach

Input: an array P of size n $+1$ where P $[$i$]$ represents the number of rows in matrix A i and

P $[$i $+1]$ represents the number of columns in matrix A i

Output: The minimum number of scalar multiplications required to multiply the entire chain

of matrices.

Example:

$$ Input: P $=[10,30,5,60]$

$$ Explanation: you need to multiply $3$ matrices A$1(1030),$ A $2(305),$ A$3(560)$

$$ There are two possible ways to parenthesize the matrix multiplication:

$($A$1$ A$2)$ A$3$

$$ First multiply A$1(1030)$ A $2(305),$ this requires $10305=1500$ scalar

multiplications

$$ Then multiply, A$3(560),$ this requires $10560=3000$ scalar multiplications

$$ Total Cost: $1500+3000=4500$

$$ A $1($A$2$ A$3)$

$$ First multiply A$2(305)$ A$3(560),$ this requires $30560=9000$ scalar

multiplications

$$ Then multiply, A$1(1030),$ this requires $103060=18000$ scalar multi$-$

plications

$$ Total Cost: $9000+18000=27000$

$$ Output: The minimum cost of matrix multiplication is $4500$ scalar multiplications cor$-$

responding to $($A$1$ A$2)$ A