Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 48

Understanding the Difference Between Array and Linked List

Lesson - 49

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 50

A Comprehensive Look at Queue in Data Structure

Lesson - 51

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 52

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 53

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 54
The Best Way to Understand the Matrix Chain Multiplication Problem

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.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

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?

MCM_recursion-img1

For the recursion based approach, you will follow the below steps:

  1. Start by placing the parenthesis in all feasible locations, calculating the cost of each placement, and returning the lowest value.
  2. Next, you will position the first set of parentheses in n-1 ways in a chain of matrices of size n.
  3. When you put a set of parentheses around a problem, you divide it into smaller subproblems.
  4. As a result, the problem has an optimal substructure and can be solved quickly using recursion.
  5. 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);

}

MCM_recursion-implementation-img1

You've now coded the recursive way to Matrix Chain Multiplication. Now, consider the problem's dynamic programming solution.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

What Is the Solution Based On Dynamic Programming to Solve the Matrix Chain Multiplication Problem?

MCM_dp-img1

You can use dynamic programming to solve the problem in pseudo-polynomial time. Here's how:

  1. First, it will divide the matrix sequence into two subsequences.
  2. You will find the minimum cost of multiplying out each subsequence.
  3. You will add these costs together and in the price of multiplying the two result matrices.
  4. 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;

}

MCM_DP-implementation-img1

This concludes this tutorial. You will now consider your next steps to solve dynamic programming issues

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

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.

About the Author

Kartik MenonKartik Menon

Kartik is an experienced content strategist and an accomplished technology marketing specialist passionate about designing engaging user experiences with integrated marketing and communication solutions.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.