Matrix Chain Multiplication | Tabulation Method

In the previous article, we learned the solution for the problem of “Matrix chain multiplication”. We had discussed the recursive and memoization solution. In this article, we will learn about the tabulation solution.

Problem Link: Matrix Chain Multiplication

Understanding the dp array

In the memoization approach, we have taken a dp[N][N]. Let us revise it and understand what dp[i][j] means.

As we have to find A1.A2.A3.A4, we will return dp[1][4] as our final answer.

Rules to write tabulation solution from the memoization solution

Write the base case.
Write down the changing parameters in terms of loops.
Write the recursive logic inside the loops.

Base Case

Let us discuss the base case first, in the memoization approach the base case was:

if (i==j) return 0
Now dp[i][i] means minimum operations to get the multiplication of Ai which means a single array which doesn’t mean anything in the context of this problem so we return 0. Therefore we write a loop to set the base case in our dp array as follows:

Changing Parameters

In tabulation, we follow a bottom-up approach that is we start from a smaller problem to the bigger problem, so here we start from (n-1)th matrix and move towards the first matrix i.e

A4_ -> A3_ -> A2_ -> A1_ .

These dashes are the matrix represented by the j pointer.

As j>i, we will start j from i+1 to N-1, thus the pattern of problem-solving becomes:

A4 -> A3.A4 -> A2.A3.A4 -> A1.A2.A3.A4.

This pattern can be achieved by writing the loops in the following way:

Recursive Logic:

Next, we just copy down the recursive logic and modify it as required.

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std;

int f(vector<int>& arr, int i, int j, vector<vector<int>>& dp){
    
    // base condition
    if(i == j)
        return 0;
        
    if(dp[i][j]!=-1)
        return dp[i][j];
    
    int mini = INT_MAX;
    
    // partioning loop
    for(int k = i; k<= j-1; k++){
        
        int ans = f(arr,i,k,dp) + f(arr, k+1,j,dp) + arr[i-1]*arr[k]*arr[j];
        
        mini = min(mini,ans);
        
    }
    
    return mini;
}


int matrixMultiplication(vector<int>& arr, int N){
    
    vector<vector<int>> dp(N,vector<int>(N,-1));
    
    for(int i=1; i<N; i++){
        dp[i][i] = 0;
    }
    
    for(int i=N-1; i>=1; i--){
        
        for(int j=i+1; j<N; j++){
            
            int mini = INT_MAX;
    
            // partioning loop
            for(int k = i; k<= j-1; k++){
                
                int ans = dp[i][k]+ dp[k+1][j] + arr[i-1]*arr[k]*arr[j];
                
                mini = min(mini,ans);
                
            }
            
            dp[i][j] = mini;
    
        }
    }
    
    return dp[1][N-1];
    
    
}

int main() {
	
	vector<int> arr = {10, 20, 30, 40, 50};
	
	int n = arr.size();
	
	cout<<"The minimum number of operations are "<<matrixMultiplication(arr,n);
	
	return 0;
}

Output:

The minimum number of operations are 38000

Time Complexity: O(N*N*N)

Reason: There are N*N states and we explicitly run a loop inside the function which will run for N times, therefore at max ‘N*N*N’ new problems will be solved.

Space Complexity: O(N*N)

Reason: We are using a 2D array ( O(N*N)) space.

Java Code

import java.util.*;

class TUF{
static int f(int[] arr, int i, int j,int[][] dp){
    
    // base condition
    if(i == j)
        return 0;
        
    if(dp[i][j]!=-1)
        return dp[i][j];
    
    int mini = Integer.MAX_VALUE;
    
    // partioning loop
    for(int k = i; k<= j-1; k++){
        
        int ans = f(arr,i,k,dp) + f(arr, k+1,j,dp) + arr[i-1]*arr[k]*arr[j];
        
        mini = Math.min(mini,ans);
        
    }
    
    return mini;
}


static int matrixMultiplication(int[] arr, int N){
    
    int [][] dp=new int[N][N];
    for(int row[]: dp)
    Arrays.fill(row,-1);
    
    for(int i=1; i<N; i++){
        dp[i][i] = 0;
    }
    
    for(int i=N-1; i>=1; i--){
        
        for(int j=i+1; j<N; j++){
            
            int mini = Integer.MAX_VALUE;
    
            // partioning loop
            for(int k = i; k<= j-1; k++){
                
                int ans = dp[i][k]+ dp[k+1][j] + arr[i-1]*arr[k]*arr[j];
                
                mini = Math.min(mini,ans);
                
            }
            
            dp[i][j] = mini;
    
        }
    }
    
    return dp[1][N-1];
    
    
}
public static void main(String args[]) {
	
    int[] arr = {10, 20, 30, 40, 50};
	
	int n = arr.length;
	
	System.out.println("The minimum number of operations are "+
        matrixMultiplication(arr,n));
	
	
}
}