1. You are given an array(arr) of positive integers of length N which represents the dimensions of N-1 matrices such that the ith matrix is of dimension arr[i-1] x arr[i]. 2. You have to find the minimum number of multiplications needed to multiply the given chain of matrices.
Input Format
A number N arr1 arr2.. N integers
Output Format
Check the sample output and question video.
Constraints
2 <= N <= 1000 1 <= arr[i] <= 500
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
3 1 2 3
Output
6