Coding Tree

Title: Dynamic programming 1 Problem statement: Implement the standard matrix chain multiplication problem The dimensions of a chain of n matrices M1, M2, …, Mn that are to be multiplied, are given as a sequence A =<a0, a1, a2, …, an+1>. The dimension of the matrix Mi is ai-1 X ai. The goal is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum. Tasks: a. Solve the problem using dynamic programming techniques. b. Print the sequence of multiplications by clearly placing parenthesis around the matrices. Example: Input: A = {10, 20, 30} Output: 6000 Explanation: There are only two matrices of dimensions 10×20 and 20×30. So, there is only one way to multiply the matrices, the cost of which is 10*20*30 = 6000. Input: A= {40, 20, 30, 10, 30} Output: 26000 Explanation: 20*30*10 + 40*20*10 + 40*10*30 = 26000.