Code in Java or Python.
Input specification: the first line contains n and the next line contains a0, ..., an, separated by spaces. You may assume that all the numbers are positive and fit in int and that n is at most 1,000.
Output specification: The output contains two lines. The first line is the optimal multiplication cost. The second line contains an optimal parenthesizing printed in the following form:
- For a matrix, print Ai, where i is the number of the matrix.
- For the multiplication of two matrices B and C, print B x C, with spaces between the matrices and the multiplication sign. Notice that B and/or C might be parenthesized expressions.
For example: ( ( A1 x ( A2 x A3 ) ) x ( A4 x A5 ) )
Problem Statement:
In the Matrix Chain Multiplication problem we are given a0, a1, . . . , an that denote the dimensions of n matrices - the i-th matrix Ai is of dimensions ai?1 × ai , and we want to find a parenthesizing that minimizes the number of operations needed to multiply A1A2 . . . An. We assume that the number of operations needed to multiply two matrices of dimensions p×q and q×r is pqr. Give an O(n 3 ) algorithm that finds a corresponding parenthesizing (more precisely, use O(n 3 ) time to find the optimal cost, then O(n) time to find the parenthesizing).