Most of the time, Dynamic Programming is essentially a more efficient version of recursion. Dynamic Programming is used to optimize any recursive solution that uses the same inputs over and over again. Subproblem results will be saved so that they do not have to be recalculated as needed in the future. This small optimization reduces the time complexity from exponential to polynomial.
Towards the end of this tutorial, you will have a better understanding of the recursion and dynamic programming approach to the Matrix Chain Multiplication problem with the essential details and actual implementations.
What Is the Problem Statement for the Matrix Chain Multiplication Problem?
You will be given a sequence of matrices; your task will determine the most efficient technique to multiply them together. The issue is not so much with performing the multiplications but with determining the order in which they should be performed.
Now, look at the recursive solution to solve the Matrix Chain Multiplication Problem.
What Is the Recursive Solution to the Matrix Chain Multiplication Problem?
For the recursion based approach, you will follow the below steps:
- Start by placing the parenthesis in all feasible locations, calculating the cost of each placement, and returning the lowest value.
- Next, you will position the first set of parentheses in n-1 ways in a chain of matrices of size n.
- When you put a set of parentheses around a problem, you divide it into smaller subproblems.
- As a result, the problem has an optimal substructure and can be solved quickly using recursion.
- The least number of n-1 placements required to multiply a chain of size n.
This is how recursion solves the Matrix Chain Multiplication problem. Now implement this solution in C++.
How Do You Implement the Recursive Solution of the Matrix Chain Multiplication Problem?
You will be given a matrix with elements as {1, 2, 3, 4, 3}. This set represents three matrices as 1x2, 2x3, 3x4, 4x3. You have to find a minimum cost to multiply these matrices.
Code:
/* A naive recursive implementation that simply
follows the above optimal substructure property */
#include <bits/stdc++.h>
using namespace std;
// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1..n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// place parentheses at different places
// between first and last matrix, recursively
// calculate count of multiplications for
// each parenthesis placement and return the
// minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, n - 1);
}
You've now coded the recursive way to Matrix Chain Multiplication. Now, consider the problem's dynamic programming solution.
What Is the Solution Based On Dynamic Programming to Solve the Matrix Chain Multiplication Problem?
You can use dynamic programming to solve the problem in pseudo-polynomial time. Here's how:
- First, it will divide the matrix sequence into two subsequences.
- You will find the minimum cost of multiplying out each subsequence.
- You will add these costs together and in the price of multiplying the two result matrices.
- These procedures will be repeated for every possible matrix split and calculate the minimum.
And this is how dynamic programming solves the problem. Now implement this solution in C++.
How Do You Implement the Solution Based On Dynamic Programming to Solve the Matrix Chain Multiplication Problem?
You will be given a matrix with elements as {10, 30, 5, 60}. This set represents three matrices as 10x30, 30x5, 5x60. You have to find a minimum cost to multiply these matrices.
Code:
//A program to implement the dynamic pro solution to MCM
#include <bits/stdc++.h>
using namespace std;
#define MAX 10
// look_up table to store the solution to already computed // subproblems
int look_up[MAX][MAX];
//A Function to multiply a given sequence of matrices //efficiently.
int mcm(int dims[], int i, int j)
{
// A base case for one matrix;
if (j <= i + 1) {
return 0;
}
// the cost of computing matrix M[i+1] in scalar multiplications M[i...j]
int min = INT_MAX;
// Solve the subproblem and save the solution in a look_up table.
if (look_up[i][j] == 0)
{
// take the minimum over each
//possible position at which the
// sequence of matrices can be split
/*
(M[i+1]) × (M[i+2]………………M[j])
(M[i+1]M[i+2]) × (M[i+3…………M[j])
…
…
(M[i+1]M[i+2]…………M[j-1]) × (M[j])
*/
for (int k = i + 1; k <= j - 1; k++)
{
// recur for `M[i+1]…M[k]` to get an `i × k` matrix
int cost = mcm(dims, i, k);
// recur for `M[k+1]…M[j]` to get an `k × j` matrix
cost += mcm(dims, k, j);
// cost to multiply two `i × k` and `k × j` matrix
cost += dims[i] * dims[k] * dims[j];
if (cost < min) {
min = cost;
}
}
look_up[i][j] = min;
}
// return the minimum cost to multiply `M[j+1]…M[j]`
return look_up[i][j];
}
// Matrix Chain Multiplication Problem
int main()
{
// Matrix `M[i]` has dimension `dims[i-1] × dims[i]` for `i = 1…n`
// input is `10 × 30` matrix, `30 × 5` matrix, `5 × 60` matrix
int dims[] = { 10, 30, 5, 60 };
int n = sizeof(dims) / sizeof(dims[0]);
cout << "The minimum cost is " << mcm(dims, 0, n - 1);
return 0;
}
This concludes this tutorial. You will now consider your next steps to solve dynamic programming issues.
Next Steps
The Subset Sum Problem should be your next step in understanding dynamic programming problems. You'll be given a set of non-negative integers and a variable sum value, and you'll have to figure out if there's a subset of that set with a sum equal to that amount.
You've come to the right place if you want to learn more about software development and succeed in it. For example, you may be interested in Simplilearn's Software Development Courses, delivered in partnership with Caltech CTME and IIT-Kanpur. These courses cover Data Structures and Algorithms fundamentals to advanced subjects like Competitive Programming. As a software engineer, this course covers data structures like trees, graphs, and queues.
If you have any comments or questions about this "Matrix Chain Multiplication Problem" tutorial, please leave them in the comments below. Our skilled staff will review them and get back to you as quickly as possible.
