Dynamic Programming solves problems by combining the solutions to subproblems just like the divide and conquer method. Dynamic programming method is used to solve the problem of multiplication of a chain of matrices so that the fewest total scalar multiplications are performed.
Given a chain (A1, A2, A3, A4….An) of n matrices, we wish to compute the product. A product of matrices is fully parenthesized if it is either a single matrix or the product of fully parenthesized matrix products, surrounded by parenthesis. Since, matrix multiplication is associative all parenthesizations yield the same product. But, the way we parenthesize a chain of matrices have an impact on the cost of evaluating the product. We divide a chain of matrices to be multiplied into two optimal sub-chains, and then the optimal parenthesizations of the sub-chains must be composed of optimal chains.
A block of memory cache is used to store the result of the function for specific values. If cache[i][j] = -1 then we do not know the result. If it is some number then that denotes the return value of multiply (i,j). We store it to avoid computing the same again.
Input Format: First integer must be the number of matrices. It has to be followed by rows of first matrix, columns of first matrix, columns for second matrix, columns for third matrix and so on.
Complete Tutorial with Examples :
Related Tutorials (common examples of Dynamic Programming):
Some Important Data Structures and Algorithms, at a glance:
Basic Data Structures and Algorithms
Sorting- at a glance
Computer Science >