Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered. Matrix-chain multiplication can be solved using Dynamic programming.
Matrix-chain multiplication
Given a sequence of matrices, find the most efficient way to multiply these matrices together. We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same.
We are given a sequence (chain) 
A1, A2, . . ., An
of n matrices to be multiplied, and we wish to compute the product
A = A1 x A2 x..x An
The way we parenthesize a chain of matrices can have a dramatic impact on the cost of evaluating the product. To illustrate the different costs incurred by different parenthesizations of a matrix product, consider the problem of a chain A1, A2, A3 of three matrices. Suppose that the dimensions of the matrices are 10 X 100,100 
5, and 5 50, respectively. If we multiply according to the parenthesization ((A1A2)A3), we perform 10 
100 5 = 5000 scalar multiplications to compute the 10 X 5 matrix product A1A2, plus another 10 5 50 = 2500 scalar multiplications to multiply this matrix by A3, for a total of 7500 scalar multiplications. If instead we multiply according to the parenthesization (A1(A2A3)), we perform 100 5 50 = 25,000 scalar multiplications to compute the 100 X 50 matrix product A2A3, plus another 10 100 50 = 50,000 scalar multiplications to multiply A1 by this matrix, for a total of 75,000 scalar multiplications. Thus, computing the product according to the first parenthesization is 10 times faster.
The matrix-chain multiplication problem can be stated as follows: given a chain A1, A2, . . . , An of n matrices, where for i = 1, 2, . . . , n , matrix Ai has dimension pi – 1 X pi, fully parenthesize the product A1 A2…An in a way that minimizes the number of scalar multiplications.
The first step of the dynamic-programming paradigm is to characterize the structure of an optimal solution. For the matrix-chain multiplication problem, we can perform this step as follows. For convenience, let us adopt the notation Ai..j for the matrix that results from evaluating the product AiAi + 1 Aj. An optimal parenthesization of the product A1A2 An splits the product between Ak and Ak + 1 for some integer k in the range 1 
k < n . That is, for some value of k, we first compute the matrices A1..k and Ak + 1..n and then multiply them together to produce the final product A1..n. The cost of this optimal parenthesization is thus the cost of computing the matrix A1..k, plus the cost of computing Ak + 1..n, plus the cost of multiplying them together.
We observed that an optimal parenthesization of A1 A2 An that splits the product between Akand Ak + 1 contains within it optimal solutions to the problems of parenthesizing A1A2 A k and Ak + 1Ak + 2. . . An. The technique that we used to show that subproblems have optimal solutions is typical.
Reference :-