__Introduction__

__Introduction__

Dynamic Programming is a class of algorithms that comes into the picture wherever there is __Recursion__ and repeating subproblems. It stores the result of the subproblems which are already computed. So that we donâ€™t have to do the repetitive work. Simply put, Dynamic Programming says us to solve only unique subproblems. In this blog, we will discuss a standard DP problem namely Matrix Chain Multiplication. We will try solving it in the most optimal way in terms of time and space complexity. So let us look at the problem statement and various algorithms to solve the problem.

__Problem Statement__

__Problem Statement__

Given â€˜Nâ€™ matrices of varying dimensions, which are multiplication compatible, find an order to multiply them such that the number of unit operations is minimized. In short, we need to find the most efficient way to multiply the matrices.

__Example__

__Example__

Given three matrices â€˜Aâ€™, â€˜Bâ€™, and â€˜Câ€™ having dimensions 10 x 20, 20 x 15, and 15 x 30, respectively. We need to multiply A, B, and C. Now there are two ways in which we can multiply them.

1. A * (B * C): The dimension of matrix A: 10 x 20, B: 20 x 15, C: 15 x 30. Therefore, the cost fof multiplication of B(20 x 15) and C(15 x 30) is BC(20 x 30) = 20 * 15 * 30 = 9000. Now, multiplying A(10 x 20) and B(20 x 30), the multiplication cost will be ABC(10 x 30) = 10 x 20 x 30 = 6000. Therefore, the total multiplication cost = 6000 + 9000 = 15000.

2. (A * B) * C : Now, let us first multiply matrices â€˜Aâ€™ and â€˜Bâ€™ which will have cost of 10 * 20 * 15 associated with it. Then, we will multiply matrices AB and C, which has the cost 10 * 15 * 30. The the total multiplication cost = 10 * 20 * 15 + 10 * 15 * 30 = 3000 + 4500 = 7500.

Thus in case (1), there are 15000 unit multiplications whereas in case (2), there are only 7500 unit multiplications. These are half than case (a). Thus we have just reduced the time taken by half. In conclusion, the order of multiplication has a significant impact on calculation cost. When the number of matrices and their dimensions increase, this saves a lot of time.

Let us consider the example of four matrices. Have a look at the picture shown below.

So, as we can see in the above image, there are five ways to multiply the four matrices. We need to choose the most optimal amongst them. We need to choose one of the N - 1 position to put parenthesis. Thus after adding the parenthesis, our problem divides into two smaller subproblems. As a result, we can use a recursive approach to solve these smaller subproblems.

Let us look at the recursive implementation of the problem above.