Dada una array p[] de tamaño n , que representa la string de arrays tal que la i-ésima array A i es de dimensión p[i-1] xp[I], donde i está en el rango de 1 a n – 1 . La tarea es encontrar el número mínimo de multiplicaciones necesarias para multiplicar la string.
Ejemplo:
Entrada: p[] = {40, 20, 30, 10, 30}
Salida: 26000
Explicación: Hay 4 arrays de dimensiones 40×20, 20×30, 30×10 y 10×30. Sean las 4 arrays de entrada A, B, C y D. El número mínimo de multiplicaciones se obtiene poniendo paréntesis de la siguiente manera (A(BC))D –> 20*30*10 + 40*20*10 + 40* 10*30Entrada: p[] = {10, 20, 30, 40, 30}
Salida: 30000
Explicación: Hay 4 arrays de dimensiones 10×20, 20×30, 30×40 y 40×30. Sean las 4 arrays de entrada A, B, C y D. El número mínimo de multiplicaciones se obtiene poniendo paréntesis de la siguiente manera ((AB)C)D –> 10*20*30 + 10*30*40 + 10* 40*30Entrada: p[] = {10, 20, 30}
Salida: 6000
Explicación: Solo hay dos arrays de dimensiones 10×20 y 20×30. Entonces solo hay una forma de multiplicar las arrays, cuyo costo es 10*20*30
Aquí hay algunas ilustraciones más del enunciado del problema: Tenemos muchas opciones para multiplicar una string de arrays porque la multiplicación de arrays es asociativa. En otras palabras, no importa cómo pongamos entre paréntesis el producto, el resultado será el mismo.
Si tuviéramos cuatro arrays A, B, C y D, tendríamos:
(ABC)D = (AB)(CD) = A(BCD) = ….
Sin embargo, el orden en que ponemos el producto entre paréntesis afecta el número de operaciones aritméticas simples necesarias para calcular el producto o la eficiencia.
Por ejemplo: suponga que A es una array de 10 × 30, B es una array de 30 × 5 y C es una array de 5 × 60. Después,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operaciones
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operaciones.
Claramente, el primer paréntesis requiere menos número de operaciones.
Hemos discutido una solución O (n ^ 3) para el problema de multiplicación de strings de arrays .
Nota: La siguiente solución no funciona en muchos casos. Por ejemplo: para la entrada {2, 40, 2, 40, 5}, la respuesta correcta es 580 pero este método devuelve 720
Hay otro enfoque similar para resolver este problema. Enfoque más intuitivo y recursivo.
Supongamos que hay el siguiente método disponible
minCost(M1, M2) -> devuelve el costo mínimo de multiplicar las arrays M1 y M2
Luego, para cualquier producto enstringdo de arrays como,
M 1 .M 2 .M 3 .M 4 …M n
costo mínimo de string = min(minCost(M 1 , M 2 .M 3 …M n ), minCost(M 1 .M 2 ..M n-1 , M n ))
Ahora tenemos dos substrings (subproblemas):
M 2 . M 3 …M n
M 1 .M 2 ..Mn-1
C++
// CPP program to implement optimized matrix chain multiplication problem.
#include<iostream>
using namespace std;
// Matrix Mi has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra row and one extra column are allocated in
dp[][]. 0th row and 0th column of dp[][] are not used */
int dp[n][n];
/* dp[i, j] = Minimum number of scalar multiplications needed to compute the matrix M[i]M[i+1]...M[j]
= M[i..j] where dimension of M[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (int i=1; i<n; i++)
dp[i][i] = 0;
// Simply following above recursive formula.
for (int L=1; L<n-1; L++)
for (int i=1; i<n-L; i++)
dp[i][i+L] = min(dp[i+1][i+L] + p[i-1]*p[i]*p[i+L],
dp[i][i+L-1] + p[i-1]*p[i+L-1]*p[i+L]);
return dp[1][n-1];
}
// Driver code
int main()
{
int arr[] = {10, 20, 30, 40, 30} ;
int size = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, size));
return 0;
}
Java
// Java program to implement optimized matrix chain multiplication problem.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// Matrix Mi has dimension p[i-1] x p[i] for i = 1..n
static int MatrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra row and one extra column are
allocated in dp[][]. 0th row and 0th column of dp[][] are not used */
int [][]dp=new int[n][n];
/* dp[i, j] = Minimum number of scalar multiplications needed to compute the matrix M[i]M[i+1]...M[j]
= M[i..j] where dimension of M[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (int i=1; i<n; i++)
dp[i][i] = 0;
// Simply following above recursive formula.
for (int L=1; L<n-1; L++)
for (int i=1; i<n-L; i++)
dp[i][i+L] = Math.min(dp[i+1][i+L] + p[i-1]*p[i]*p[i+L],
dp[i][i+L-1] + p[i-1]*p[i+L-1]*p[i+L]);
return dp[1][n-1];
}
// Driver code
public static void main(String args[])
{
int arr[] = {10, 20, 30, 40, 30} ;
int size = arr.length;
System.out.print("Minimum number of multiplications is "+
MatrixChainOrder(arr, size));
}
}
Python3
# Python3 program to implement optimized
# matrix chain multiplication problem.
# Matrix Mi has dimension
# p[i-1] x p[i] for i = 1..n
def MatrixChainOrder(p, n):
# For simplicity of the program, one
# extra row and one extra column are
# allocated in dp[][]. 0th row and
# 0th column of dp[][] are not used
dp = [[0 for i in range(n)]
for i in range(n)]
# dp[i, j] = Minimum number of scalar
# multiplications needed to compute
# the matrix M[i]M[i+1]...M[j] = M[i..j]
# where dimension of M[i] is p[i-1] x p[i]
# cost is zero when multiplying one matrix.
for i in range(1, n):
dp[i][i] = 0
# Simply following above recursive formula.
for L in range(1, n - 1):
for i in range(n - L):
dp[i][i + L] = min(dp[i + 1][i + L] +
p[i - 1] * p[i] * p[i + L],
dp[i][i + L - 1] +
p[i - 1] * p[i + L - 1] * p[i + L])
return dp[1][n - 1]
# Driver code
arr = [10, 20, 30, 40, 30]
size = len(arr)
print("Minimum number of multiplications is",
MatrixChainOrder(arr, size))
# This code is contributed
# by sahishelangia
C#
// C# program to implement optimized
// matrix chain multiplication problem.
using System;
class GFG
{
// Matrix Mi has dimension
// p[i-1] x p[i] for i = 1..n
static int MatrixChainOrder(int []p, int n)
{
/* For simplicity of the program,
one extra row and one extra
column are allocated in dp[][].
0th row and 0th column of dp[][]
are not used */
int [,]dp = new int[n, n];
/* dp[i, j] = Minimum number of scalar
multiplications needed to compute
the matrix M[i]M[i+1]...M[j] = M[i..j]
where dimension of M[i] is p[i-1] x p[i] */
// cost is zero when multiplying
// one matrix.
for (int i = 1; i < n; i++)
dp[i, i] = 0;
// Simply following above
// recursive formula.
for (int L = 1; L < n - 1; L++)
for (int i = 1; i < n - L; i++)
dp[i, i + L] = Math.Min(dp[i + 1, i + L] +
p[i - 1] * p[i] * p[i + L],
dp[i, i + L - 1] + p[i - 1] *
p[i + L - 1] * p[i + L]);
return dp[1, n - 1];
}
// Driver code
public static void Main()
{
int []arr = {10, 20, 30, 40, 30} ;
int size = arr.Length;
Console.WriteLine("Minimum number of multiplications is " +
MatrixChainOrder(arr, size));
}
}
// This code is contributed by anuj_67
PHP
<?php
// PHP program to implement optimized
// matrix chain multiplication problem.
// Matrix Mi has dimension
// p[i-1] x p[i] for i = 1..n
function MatrixChainOrder($p, $n)
{
/* For simplicity of the program,
one extra row and one extra column
are allocated in dp[][]. 0th row
and 0th column of dp[][] are not used */
$dp = array();
/* dp[i, j] = Minimum number of scalar
multiplications needed to
compute the matrix M[i]M[i+1]...M[j]
= M[i..j] where dimension of M[i]
is p[i-1] x p[i] */
// cost is zero when multiplying
// one matrix.
for ($i=1; $i<$n; $i++)
$dp[$i][$i] = 0;
// Simply following above
// recursive formula.
for ($L = 1; $L < $n - 1; $L++)
for ($i = 1; $i < $n - $L; $i++)
$dp[$i][$i + $L] = min($dp[$i + 1][$i + $L] + $p[$i - 1] *
$p[$i] * $p[$i + $L],
$dp[$i][$i + $L - 1] + $p[$i - 1] *
$p[$i + $L - 1] * $p[$i + $L]);
return $dp[1][$n - 1];
}
// Driver code
$arr = array(10, 20, 30, 40, 30) ;
$size = sizeof($arr);
echo "Minimum number of multiplications is ".
MatrixChainOrder($arr, $size);
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// Javascript program to implement optimized
// matrix chain multiplication problem.
// Matrix Mi has dimension p[i-1] x p[i] for i = 1..n
function MatrixChainOrder(p, n)
{
/* For simplicity of the program, one extra row
and one extra column are allocated in
dp[][]. 0th row and 0th column of dp[][] are not used */
var dp = Array.from(Array(n), ()=> Array(n));
/* dp[i, j] = Minimum number of scalar multiplications
needed to compute the matrix M[i]M[i+1]...M[j]
= M[i..j] where dimension
of M[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (var i=1; i<n; i++)
dp[i][i] = 0;
// Simply following above recursive formula.
for (var L=1; L<n-1; L++)
for (var i=1; i<n-L; i++)
dp[i][i+L] = Math.min(dp[i+1][i+L] +
p[i-1]*p[i]*p[i+L],
dp[i][i+L-1] + p[i-1]*p[i+L-1]*p[i+L]);
return dp[1][n-1];
}
// Driver code
var arr = [10, 20, 30, 40, 30];
var size = arr.length;
document.write("Minimum number of multiplications is "+
MatrixChainOrder(arr, size));
</script>
Minimum number of multiplications is 30000
Complejidad del tiempo: O(n 2 )
Impresión de corchetes en la multiplicación de strings de arrays
Gracias a Rishi_Lazy por proporcionar la solución optimizada anterior.