Posted on by Kalkicode
Code Dynamic Programming

# Matrix chain multiplication using dynamic programming

Matrix Chain Multiplication is a classic problem in computer science that involves finding the most efficient way to multiply a sequence of matrices. Given a chain of matrices, we want to determine the optimal order of multiplication that minimizes the total number of scalar multiplications required. This problem has various real-world applications, including optimization of matrix computations in computer graphics, numerical simulations, and machine learning algorithms.

### Problem Statement:

Given a sequence of matrices, we need to find the minimum number of scalar multiplications required to multiply them together in a specific order. Each matrix has dimensions represented by rows and columns. The goal is to determine the optimal parenthesization of the matrices to minimize the total cost of multiplication.

### Solution Approach:

To solve the Matrix Chain Multiplication problem, we can use the dynamic programming technique. The key idea is to break down the problem into smaller subproblems and build the solution incrementally.

We can define a recursive function or use an iterative approach to calculate the minimum cost of multiplying matrices. The dynamic programming solution involves building a matrix, often called the cost matrix or table, to store the optimal costs for multiplying subchains of matrices.

### Algorithm:

1. Create a 2D matrix, 'c', of size n x n, where n is the number of matrices in the chain.
2. Initialize the diagonal elements of 'c' to 0 since multiplying a single matrix has no cost.
3. Iterate over the 'c' matrix diagonally, from bottom-left to top-right, for increasing chain lengths (from 2 to n).
4. For each diagonal element 'c[i][j]', calculate the minimum cost by considering different partition points 'k' between 'i' and 'j' (i ≤ k < j).
5. The minimum cost for 'c[i][j]' can be computed as c[i][k] + c[k+1][j] + dims[i-1] * dims[k] * dims[j], where dims is an array representing the dimensions of the matrices.
6. Store the minimum cost in 'c[i][j]'.
7. The top-right element of 'c' will represent the minimum cost of multiplying the entire matrix chain.

## Code solution

// 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[])
{
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;

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

*/
}
}

#### Output

2952
3840
#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()
{
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)
{
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;
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
*/
}
}

#### 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()
{
\$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);
\$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
*/
}
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 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;
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
*/
}
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() :
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()
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
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
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;
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
*/
}
}

#### 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 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 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();
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
*/
}

2952
3840

### Time Complexity:

The dynamic programming approach to solve the Matrix Chain Multiplication problem has a time complexity of O(n^3), where n is the number of matrices in the chain. This is because we iterate over the 'c' matrix of size n x n and perform calculations for each element.

We discussed the Matrix Chain Multiplication problem and its solution using dynamic programming. We explained the problem statement, the solution approach, and provided the code implementation. The dynamic programming technique allows us to solve the problem efficiently by breaking it down into smaller subproblems and building the solution incrementally. The time complexity of the solution is O(n^3), where n is the number of matrices in the chain. This approach provides an optimal solution for minimizing the number of scalar multiplications in matrix chain multiplication.

## 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.

Categories
Relative Post