Dynamic Programming Solution for Matrix Chain Multiplication using Memoization

Below is the recursion tree for the 2nd example of the above recursive approach:

If observed carefully you can find the following two properties:

1) Optimal Substructure: In the above case, we are breaking the bigger groups into smaller subgroups and solving them to finally find the minimum number of multiplications. Therefore, it can be said that the problem has optimal substructure property.

2) Overlapping Subproblems: We can see in the recursion tree that the same subproblems are called again and again and this problem has the Overlapping Subproblems property.

So Matrix Chain Multiplication problem has both properties of a dynamic programming problem. So recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in a bottom up manner.

Follow the below steps to solve the problem:

Build a matrix dp[][] of size N*N for memoization purposes.
Use the same recursive call as done in the above approach:
- When we find a range (i, j) for which the value is already calculated, return the minimum value for that range (i.e., dp[i][j]).
- Otherwise, perform the recursive calls as mentioned earlier.
The value stored at dp[0][N-1] is the required answer.

Below is the implementation of the above approach

C++

// C++ program using memoization
#include <bits/stdc++.h>
using namespace std;
int dp[100][100];
 
// Function for matrix chain multiplication
int matrixChainMemoised(int* p, int i, int j)
{
    if (i == j) 
    {
        return 0;
    }
    if (dp[i][j] != -1) 
    {
        return dp[i][j];
    }
    dp[i][j] = INT_MAX;
    for (int k = i; k < j; k++) 
    {
        dp[i][j] = min(
            dp[i][j], matrixChainMemoised(p, i, k)
                     + matrixChainMemoised(p, k + 1, j)
                       + p[i - 1] * p[k] * p[j]);
    }
    return dp[i][j];
}
int MatrixChainOrder(int* p, int n)
{
    int i = 1, j = n - 1;
    return matrixChainMemoised(p, i, j);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    memset(dp, -1, sizeof dp);
 
    cout << "Minimum number of multiplications is "
         << MatrixChainOrder(arr, n);
}
 
// This code is contributed by Sumit_Yadav

Java

// Java program using memoization 
import java.io.*;
import java.util.*;
class GFG
{
 
  static int[][] dp = new int[100][100];
 
  // Function for matrix chain multiplication 
  static int matrixChainMemoised(int[] p, int i, int j) 
  { 
    if (i == j)  
    { 
      return 0; 
    } 
    if (dp[i][j] != -1)  
    { 
      return dp[i][j]; 
    } 
    dp[i][j] = Integer.MAX_VALUE; 
    for (int k = i; k < j; k++)  
    { 
      dp[i][j] = Math.min( 
        dp[i][j], matrixChainMemoised(p, i, k) 
        + matrixChainMemoised(p, k + 1, j) 
        + p[i - 1] * p[k] * p[j]); 
    } 
    return dp[i][j]; 
  } 
 
  static int MatrixChainOrder(int[] p, int n) 
  { 
    int i = 1, j = n - 1; 
    return matrixChainMemoised(p, i, j); 
  } 
 
  // Driver Code
  public static void main (String[] args)
  {
 
    int arr[] = { 1, 2, 3, 4 }; 
    int n= arr.length;
 
    for (int[] row : dp) 
      Arrays.fill(row, -1); 
 
    System.out.println("Minimum number of multiplications is " + MatrixChainOrder(arr, n));
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python program using memoization 
import sys
dp = [[-1 for i in range(100)] for j in range(100)]
 
# Function for matrix chain multiplication 
def matrixChainMemoised(p, i, j):
    if(i == j):
        return 0
     
    if(dp[i][j] != -1):
        return dp[i][j]
     
    dp[i][j] = sys.maxsize
     
    for k in range(i,j):
        dp[i][j] = min(dp[i][j], matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j)+ p[i - 1] * p[k] * p[j])
     
    return dp[i][j]
 
def MatrixChainOrder(p,n):
    i = 1
    j = n - 1   
    return matrixChainMemoised(p, i, j)
 
# Driver Code
arr = [1, 2, 3, 4]
n = len(arr)
print("Minimum number of multiplications is",MatrixChainOrder(arr, n))
 
# This code is contributed by rag2127

C#

// C# program using memoization
using System;
class GFG 
{
     
    static int[,] dp = new int[100, 100];
  
  // Function for matrix chain multiplication 
  static int matrixChainMemoised(int[] p, int i, int j) 
  { 
    if (i == j)  
    { 
      return 0; 
    } 
    if (dp[i, j] != -1)  
    { 
      return dp[i, j]; 
    } 
    dp[i, j] = Int32.MaxValue; 
    for (int k = i; k < j; k++)  
    { 
      dp[i, j] = Math.Min( 
        dp[i, j], matrixChainMemoised(p, i, k) 
        + matrixChainMemoised(p, k + 1, j) 
        + p[i - 1] * p[k] * p[j]); 
    } 
    return dp[i,j]; 
  } 
  
  static int MatrixChainOrder(int[] p, int n) 
  { 
    int i = 1, j = n - 1; 
    return matrixChainMemoised(p, i, j); 
  } 
   
  // Driver code
  static void Main()
  {
    int[] arr = { 1, 2, 3, 4 }; 
    int n = arr.Length;
     
    for(int i = 0; i < 100; i++)
    {
        for(int j = 0; j < 100; j++)
        {
            dp[i, j] = -1;
        }
    }
  
    Console.WriteLine("Minimum number of multiplications is " + 
                      MatrixChainOrder(arr, n));
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
 
// Javascript program using memoization 
let dp = new Array(100);
for(var i = 0; i < dp.length; i++) 
{
    dp[i] = new Array(2);
}
 
// Function for matrix chain multiplication 
function matrixChainMemoised(p, i, j) 
{ 
    if (i == j)  
    { 
        return 0; 
    } 
    if (dp[i][j] != -1)  
    { 
        return dp[i][j]; 
    } 
     
    dp[i][j] = Number.MAX_VALUE; 
    for(let k = i; k < j; k++)  
    { 
        dp[i][j] = Math.min(
            dp[i][j], matrixChainMemoised(p, i, k) + 
                      matrixChainMemoised(p, k + 1, j) +
                      p[i - 1] * p[k] * p[j]); 
    } 
    return dp[i][j]; 
} 
 
function MatrixChainOrder(p, n) 
{ 
    let i = 1, j = n - 1; 
    return matrixChainMemoised(p, i, j); 
} 
 
// Driver code
let arr = [ 1, 2, 3, 4 ]; 
let n = arr.length;
 
for(var i = 0; i < dp.length; i++) 
{
    for(var j = 0; j < dp.length; j++)
    {
        dp[i][j] = -1;
    }
}
 
document.write("Minimum number of multiplications is " +
               MatrixChainOrder(arr, n));
                
// This code is contributed by target_2
 
</script>

Output

Minimum number of multiplications is 18

Time Complexity: O(N³ )
Auxiliary Space: O(N²) ignoring recursion stack space

Matrix Chain Multiplication | DP-8

Given the dimension of a sequence of matrices in an array arr[], where the dimension of the i^th matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum.

Examples:

Input: arr[] = {40, 20, 30, 10, 30}
Output: 26000
Explanation:There are 4 matrices of dimensions 40×20, 20×30, 30×10, 10×30.
Let the input 4 matrices be A, B, C and D.
The minimum number of multiplications are obtained by
putting parenthesis in following way (A(BC))D.
The minimum is 20*30*10 + 40*20*10 + 40*10*30

Input: arr[] = {1, 2, 3, 4, 3}
Output: 30
Explanation: There are 4 matrices of dimensions 1×2, 2×3, 3×4, 4×3.
Let the input 4 matrices be A, B, C and D.
The minimum number of multiplications are obtained by
putting parenthesis in following way ((AB)C)D.
The minimum number is 1*2*3 + 1*3*4 + 1*4*3 = 30

Input: arr[] = {10, 20, 30}
Output: 6000
Explanation: There are only two matrices of dimensions 10×20 and 20×30.
So there is only one way to multiply the matrices, cost of which is 10*20*30

Dynamic Programming Solution for Matrix Chain Multiplication using Memoization

C++

Java

Python3

C#

Javascript

Matrix Chain Multiplication | DP-8

Categories

Contact US

Dynamic Programming Solution for Matrix Chain Multiplication using Memoization

C++

Java

Python3

C#

Javascript

Matrix Chain Multiplication | DP-8

Similar Reads

Categories

Contact US