Skip to main content

Matrix chain multiplication using dynamic programming

Here given code implementation process.

// C Program
// Matrix chain multiplication
#include <stdio.h>
#include <limits.h>

int matrixChainMultiplication(int dims[], int n)
{
    int c[n][n];
    int j = 0;
    int cost = 0;
    for (int i = 1; i < n; ++i)
    {
        c[i][i] = 0;
    }
    for (int len = 2; len < n; ++len)
    {
        for (int i = 1; i < n - len + 1; ++i)
        {
            j = i + len - 1;
            c[i][j] = INT_MAX;
            for (int k = i; k <= j - 1 && j < n; ++k)
            {
                cost = c[i][k] + c[k + 1][j] + 
                  dims[i - 1] * dims[k] * dims[j];
                if (cost < c[i][j])
                {
                    c[i][j] = cost;
                }
            }
        }
    }
    return c[1][n - 1];
}
int main()
{
        int dims1[] = {
            10 , 16 , 12 , 6 , 14
        };
        int dims2[] = {
            8 , 20 , 16 , 10 , 6
        };
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D
            (16×12×6) + (10×16×6) + (10×6×14)
             =  2952  
        */
        int n = sizeof(dims1) / sizeof(dims1[0]);
        printf("\n %d",matrixChainMultiplication(dims1, n));
        n = sizeof(dims2) / sizeof(dims2[0]);
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6
            A(B(CD)) =  3840
            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
        */
        printf("\n %d",matrixChainMultiplication(dims2, n));
    return 0;
}

Output

 2952
 3840
// Java Program 
// Matrix chain multiplication using dynamic programming
public class Multiplication
{
    public int matrixChainMultiplication(int[] dims, int n)
    {
        int[][] c = new int[n][n];
        int j = 0;
        int cost = 0;
        for (int i = 1; i < n; ++i)
        {
            c[i][i] = 0;
        }
        for (int len = 2; len < n; ++len)
        {
            for (int i = 1; i < n - len + 1; ++i)
            {
                j = i + len - 1;

                c[i][j] = Integer.MAX_VALUE;
                
                for (int k = i; k <= j - 1 && j < n; ++k)
                {
                    cost = c[i][k] + c[k + 1][j] + 
                      dims[i - 1] * dims[k] * dims[j];
                    if (cost < c[i][j])
                    {
                        c[i][j] = cost;
                    }
                }
            }
        }
        return c[1][n - 1];
    }
    public static void main(String args[])
    {
        Multiplication task = new Multiplication();
        int[] dims1 = {
            10 , 16 , 12 , 6 , 14
        };

        int[] dims2 = 
        {
            8 , 20 , 16 , 10 , 6
        };

        
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D

            (16×12×6) + (10×16×6) + (10×6×14)
             =  2952  
        */
        int n = dims1.length;
        System.out.print("\n " + task.matrixChainMultiplication(dims1, n));
    
        n = dims2.length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6

            A(B(CD)) =  3840

            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840

        */
        System.out.print("\n " + task.matrixChainMultiplication(dims2, n));
    }
}

Output

 2952
 3840
// Include header file
#include <iostream>

#include <limits.h>

using namespace std;
// C++ Program
// Matrix chain multiplication using dynamic programming
class Multiplication
{
    public: int matrixChainMultiplication(int dims[], int n)
    {
        int c[n][n];
        int j = 0;
        int cost = 0;
        for (int i = 1; i < n; ++i)
        {
            c[i][i] = 0;
        }
        for (int len = 2; len < n; ++len)
        {
            for (int i = 1; i < n - len + 1; ++i)
            {
                j = i + len - 1;
                c[i][j] = INT_MAX;
                for (int k = i; k <= j - 1 && j < n; ++k)
                {
                    cost = c[i][k] + c[k + 1][j] + 
                      dims[i - 1] *dims[k] *dims[j];
                    if (cost < c[i][j])
                    {
                        c[i][j] = cost;
                    }
                }
            }
        }
        return c[1][n - 1];
    }
};
int main()
{
    Multiplication *task = new Multiplication();
    int dims1[] = {
        10 , 16 , 12 , 6 , 14
    };
    int dims2[] = {
        8 , 20 , 16 , 10 , 6
    };
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    int n = sizeof(dims1) / sizeof(dims1[0]);
    cout << "\n " << task->matrixChainMultiplication(dims1, n);
    n = sizeof(dims2) / sizeof(dims2[0]);
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    cout << "\n " << task->matrixChainMultiplication(dims2, n);
    return 0;
}

Output

 2952
 3840
// Include namespace system
using System;
// Csharp Program
// Matrix chain multiplication using dynamic programming
public class Multiplication
{
    public int matrixChainMultiplication(int[] dims, int n)
    {
        int[,] c = new int[n,n];
        int j = 0;
        int cost = 0;
        for (int i = 1; i < n; ++i)
        {
            c[i,i] = 0;
        }
        for (int len = 2; len < n; ++len)
        {
            for (int i = 1; i < n - len + 1; ++i)
            {
                j = i + len - 1;
                c[i,j] = int.MaxValue;
                for (int k = i; k <= j - 1 && j < n; ++k)
                {
                    cost = c[i,k] + c[k + 1,j] + 
                      dims[i - 1] * dims[k] * dims[j];
                    if (cost < c[i,j])
                    {
                        c[i,j] = cost;
                    }
                }
            }
        }
        return c[1,n - 1];
    }
    public static void Main(String[] args)
    {
        Multiplication task = new Multiplication();
        int[] dims1 = {
            10 , 16 , 12 , 6 , 14
        };
        int[] dims2 = {
            8 , 20 , 16 , 10 , 6
        };
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D
            (16×12×6) + (10×16×6) + (10×6×14)
             =  2952  
        */
        int n = dims1.Length;
        Console.Write("\n " + task.matrixChainMultiplication(dims1, n));
        n = dims2.Length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6
            A(B(CD)) =  3840
            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
        */
        Console.Write("\n " + task.matrixChainMultiplication(dims2, n));
    }
}

Output

 2952
 3840
package main
import "math"
import "fmt"
// Go Program
// Matrix chain multiplication using dynamic programming

func matrixChainMultiplication(dims[] int, n int) int {
    var c = make([][] int, n)
    for i :=0; i < n;i++{
        c[i] = make([]int, n)
    }
    var j int = 0
    var cost int = 0
    for i := 1 ; i < n ; i++ {
        c[i][i] = 0
    }
    for len := 2 ; len < n ; len++ {
        for i := 1 ; i < n - len + 1 ; i++ {
            j = i + len - 1
            c[i][j] = math.MaxInt64
            for k := i ; k <= j - 1 && j < n ; k++ {
                cost = c[i][k] + c[k + 1][j] + 
                dims[i - 1] * dims[k] * dims[j]
                if cost < c[i][j] {
                    c[i][j] = cost
                }
            }
        }
    }
    return c[1][n - 1]
}
func main() {
    
    var dims1 = [] int { 10 , 16 , 12 , 6 , 14 }
    var dims2 = [] int { 8 , 20 , 16 , 10 , 6 }
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    var n int = len(dims1)
    fmt.Print("\n ", matrixChainMultiplication(dims1, n))
    n = len(dims2)
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    fmt.Print("\n ", matrixChainMultiplication(dims2, n))
}

Output

 2952
 3840
<?php
// Php Program
// Matrix chain multiplication using dynamic programming
class Multiplication
{
    public  function matrixChainMultiplication($dims, $n)
    {
        $c = array_fill(0, $n, array_fill(0, $n, 0));
        $j = 0;
        $cost = 0;

        for ($len = 2; $len < $n; ++$len)
        {
            for ($i = 1; $i < $n - $len + 1; ++$i)
            {
                $j = $i + $len - 1;
                $c[$i][$j] = PHP_INT_MAX;
                for ($k = $i; $k <= $j - 1 && $j < $n; ++$k)
                {
                    $cost = $c[$i][$k] + $c[$k + 1][$j] + 
                      $dims[$i - 1] * $dims[$k] * $dims[$j];
                    if ($cost < $c[$i][$j])
                    {
                        $c[$i][$j] = $cost;
                    }
                }
            }
        }
        return $c[1][$n - 1];
    }
}

function main()
{
    $task = new Multiplication();
    $dims1 = array(10, 16, 12, 6, 14);
    $dims2 = array(8, 20, 16, 10, 6);
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    $n = count($dims1);
    echo("\n ".$task->matrixChainMultiplication($dims1, $n));
    $n = count($dims2);
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    echo("\n ".$task->matrixChainMultiplication($dims2, $n));
}
main();

Output

 2952
 3840
// Node JS Program
// Matrix chain multiplication using dynamic programming
class Multiplication
{
    matrixChainMultiplication(dims, n)
    {
        var c = Array(n).fill(0).map(() => new Array(n).fill(0));
        var j = 0;
        var cost = 0;
        for (var i = 1; i < n; ++i)
        {
            c[i][i] = 0;
        }
        for (var len = 2; len < n; ++len)
        {
            for (var i = 1; i < n - len + 1; ++i)
            {
                j = i + len - 1;
                c[i][j] = Number.MAX_VALUE;
                for (var k = i; k <= j - 1 && j < n; ++k)
                {
                    cost = c[i][k] + c[k + 1][j] + 
                      dims[i - 1] * dims[k] * dims[j];
                    if (cost < c[i][j])
                    {
                        c[i][j] = cost;
                    }
                }
            }
        }
        return c[1][n - 1];
    }
}

function main()
{
    var task = new Multiplication();
    var dims1 = [10, 16, 12, 6, 14];
    var dims2 = [8, 20, 16, 10, 6];
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    var n = dims1.length;
    process.stdout.write("\n " + task.matrixChainMultiplication(dims1, n));
    n = dims2.length;
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    process.stdout.write("\n " + task.matrixChainMultiplication(dims2, n));
}
main();

Output

 2952
 3840
import sys
#  Python 3 Program
#  Matrix chain multiplication using dynamic programming
class Multiplication :
    def matrixChainMultiplication(self, dims, n) :
        c = [[0] * (n) for _ in range(n) ]
        j = 0
        cost = 0
        i = 1
        while (i < n) :
            c[i][i] = 0
            i += 1
        
        len = 2
        while (len < n) :
            i = 1
            while (i < n - len + 1) :
                j = i + len - 1
                c[i][j] = sys.maxsize
                k = i
                while (k <= j - 1 and j < n) :
                    cost = c[i][k] + c[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                    if (cost < c[i][j]) :
                        c[i][j] = cost
                    
                    k += 1
                
                i += 1
            
            len += 1
        
        return c[1][n - 1]
    

def main() :
    task = Multiplication()
    dims1 = [10, 16, 12, 6, 14]
    dims2 = [8, 20, 16, 10, 6]
    #   dims = [10 , 16 , 12 , 6 , 14]
    #    matri× A = 10 × 16 
    #    matri× B = 16 × 12
    #    matri× C = 12 × 6
    #    matri× D = 6 ×  14
    #    --------------------
    #    (A(BC))D
    #    (16×12×6) + (10×16×6) + (10×6×14)
    #     =  2952  
    n = len(dims1)
    print("\n ", task.matrixChainMultiplication(dims1, n), end = "")
    n = len(dims2)
    #   dims = [8 , 20 , 16 , 10 , 6]
    #    matri× A = 8 × 20
    #    matri× B = 20 × 16
    #    matri× C = 16 × 10
    #    matri× D = 10 × 6
    #    A(B(CD)) =  3840
    #    (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    print("\n ", task.matrixChainMultiplication(dims2, n), end = "")

if __name__ == "__main__": main()

Output

  2952
  3840
#  Ruby Program
#  Matrix chain multiplication using dynamic programming
class Multiplication 
    def matrixChainMultiplication(dims, n) 
        c = Array.new(n) {Array.new(n) {0}}
        j = 0
        cost = 0
        i = 1
        while (i < n) 
            c[i][i] = 0
            i += 1
        end

        len = 2
        while (len < n) 
            i = 1
            while (i < n - len + 1) 
                j = i + len - 1
                c[i][j] = (2 ** (0. size * 8 - 2))
                k = i
                while (k <= j - 1 && j < n) 
                    cost = c[i][k] + c[k + 1][j] + 
                      dims[i - 1] * dims[k] * dims[j]
                    if (cost < c[i][j]) 
                        c[i][j] = cost
                    end

                    k += 1
                end

                i += 1
            end

            len += 1
        end

        return c[1][n - 1]
    end

end

def main() 
    task = Multiplication.new()
    dims1 = [10, 16, 12, 6, 14]
    dims2 = [8, 20, 16, 10, 6]
    #   dims = [10 , 16 , 12 , 6 , 14]
    #    matri× A = 10 × 16 
    #    matri× B = 16 × 12
    #    matri× C = 12 × 6
    #    matri× D = 6 ×  14
    #    --------------------
    #    (A(BC))D
    #    (16×12×6) + (10×16×6) + (10×6×14)
    #     =  2952  
    n = dims1.length
    print("\n ", task.matrixChainMultiplication(dims1, n))
    n = dims2.length
    #   dims = [8 , 20 , 16 , 10 , 6]
    #    matri× A = 8 × 20
    #    matri× B = 20 × 16
    #    matri× C = 16 × 10
    #    matri× D = 10 × 6
    #    A(B(CD)) =  3840
    #    (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    print("\n ", task.matrixChainMultiplication(dims2, n))
end

main()

Output

 2952
 3840
// Scala Program
// Matrix chain multiplication using dynamic programming
class Multiplication()
{
    def matrixChainMultiplication(dims: Array[Int], n: Int): Int = {
        var c: Array[Array[Int]] = Array.fill[Int](n, n)(0);
        var j: Int = 0;
        var cost: Int = 0;
        var i: Int = 1;
        while (i < n)
        {
            c(i)(i) = 0;
            i += 1;
        }
        var len: Int = 2;
        while (len < n)
        {
            var i: Int = 1;
            while (i < n - len + 1)
            {
                j = i + len - 1;
                c(i)(j) = Int.MaxValue;
                var k: Int = i;
                while (k <= j - 1 && j < n)
                {
                    cost = c(i)(k) + c(k + 1)(j) + 
                      dims(i - 1) * dims(k) * dims(j);
                    if (cost < c(i)(j))
                    {
                        c(i)(j) = cost;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        return c(1)(n - 1);
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Multiplication = new Multiplication();
        var dims1: Array[Int] = Array(10, 16, 12, 6, 14);
        var dims2: Array[Int] = Array(8, 20, 16, 10, 6);
        /*
            dims = [10 , 16 , 12 , 6 , 14]
            matri× A = 10 × 16 
            matri× B = 16 × 12
            matri× C = 12 × 6
            matri× D = 6 ×  14
            --------------------
            (A(BC))D
            (16×12×6) + (10×16×6) + (10×6×14)
             =  2952  
        */
        var n: Int = dims1.length;
        print("\n " + task.matrixChainMultiplication(dims1, n));
        n = dims2.length;
        /*
            dims = [8 , 20 , 16 , 10 , 6]
            matri× A = 8 × 20
            matri× B = 20 × 16
            matri× C = 16 × 10
            matri× D = 10 × 6
            A(B(CD)) =  3840
            (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
        */
        print("\n " + task.matrixChainMultiplication(dims2, n));
    }
}

Output

 2952
 3840
import Foundation;
// Swift 4 Program
// Matrix chain multiplication using dynamic programming
class Multiplication
{
    func matrixChainMultiplication(_ dims: [Int], _ n: Int) -> Int
    {
        var c: [
            [Int]
        ] = Array(repeating: Array(repeating: 0, count: n), count: n);
        var j: Int = 0;
        var cost: Int = 0;
        
        
        var len: Int = 2;
        while (len < n)
        {
            var i: Int = 1;
            while (i < n - len + 1)
            {
                j = i + len - 1;
                c[i][j] = Int.max;
                var k: Int = i;
                while (k <= j - 1 && j < n)
                {
                    cost = c[i][k] + c[k + 1][j] + dims[i - 1] * 
                      dims[k] * dims[j];
                    if (cost < c[i][j])
                    {
                        c[i][j] = cost;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        return c[1][n - 1];
    }
}
func main()
{
    let task: Multiplication = Multiplication();
    let dims1: [Int] = [10, 16, 12, 6, 14];
    let dims2: [Int] = [8, 20, 16, 10, 6];
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    var n: Int = dims1.count;
    print("\n ", task.matrixChainMultiplication(dims1, n), terminator: "");
    n = dims2.count;
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    print("\n ", task.matrixChainMultiplication(dims2, n), terminator: "");
}
main();

Output

  2952
  3840
// Kotlin Program
// Matrix chain multiplication using dynamic programming
class Multiplication
{
    fun matrixChainMultiplication(dims: Array < Int > , n: Int): Int
    {
        var c: Array < Array < Int >> = Array(n)
        {
            Array(n)
            {
                0
            }
        };
    
        var cost: Int;
        var len: Int = 2;
        while (len < n)
        {
            var i: Int = 1;
            while (i < n - len + 1)
            {
                var j = i + len - 1;
                c[i][j] = Int.MAX_VALUE;
                var k: Int = i;
                while (k <= j - 1 && j < n)
                {
                      cost = c[i][k] + c[k + 1][j] + 
                      dims[i - 1] * dims[k] * dims[j];
                    if (cost < c[i][j])
                    {
                        c[i][j] = cost;
                    }
                    k += 1;
                }
                i += 1;
            }
            len += 1;
        }
        return c[1][n - 1];
    }
}
fun main(args: Array < String > ): Unit
{
    val task: Multiplication = Multiplication();
    val dims1: Array < Int > = arrayOf(10, 16, 12, 6, 14);
    val dims2: Array < Int > = arrayOf(8, 20, 16, 10, 6);
    /*
        dims = [10 , 16 , 12 , 6 , 14]
        matri× A = 10 × 16 
        matri× B = 16 × 12
        matri× C = 12 × 6
        matri× D = 6 ×  14
        --------------------
        (A(BC))D
        (16×12×6) + (10×16×6) + (10×6×14)
         =  2952  
    */
    var n: Int = dims1.count();
    print("\n " + task.matrixChainMultiplication(dims1, n));
    n = dims2.count();
    /*
        dims = [8 , 20 , 16 , 10 , 6]
        matri× A = 8 × 20
        matri× B = 20 × 16
        matri× C = 16 × 10
        matri× D = 10 × 6
        A(B(CD)) =  3840
        (16×10×6) + (20×16×6 ) + (8×20×6 ) = 3840
    */
    print("\n " + task.matrixChainMultiplication(dims2, n));
}

Output

 2952
 3840
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment