Dada una secuencia de arrays, encuentre la forma más eficiente de multiplicar estas arrays. El problema no es realmente realizar las multiplicaciones, sino simplemente decidir en qué orden realizar las multiplicaciones.
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. Por ejemplo, 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 la cantidad 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,
C++
/* A naive recursive implementation that simply
follows the above optimal substructure property */
#include <bits/stdc++.h>
using namespace std;
// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1..n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// place parenthesis at different places
// between first and last matrix, recursively
// calculate count of multiplications for
// each parenthesis placement and return the
// minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, n - 1);
}
// This code is contributed by Shivi_Aggarwal
C
/* A naive recursive implementation that simply
follows the above optimal substructure property */
#include <limits.h>
#include <stdio.h>
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;
// place parenthesis at different places between first
// and last matrix, recursively calculate count of
// multiplications for each parenthesis placement and
// return the minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, 1, n - 1));
getchar();
return 0;
}
Java
/* A naive recursive implementation that simply follows
the above optimal substructure property */
class MatrixChainMultiplication {
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
static int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int min = Integer.MAX_VALUE;
// place parenthesis at different places between
// first and last matrix, recursively calculate
// count of multiplications for each parenthesis
// placement and return the minimum count
for (int k = i; k < j; k++)
{
int count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[] { 1, 2, 3, 4, 3 };
int n = arr.length;
System.out.println(
"Minimum number of multiplications is "
+ MatrixChainOrder(arr, 1, n - 1));
}
}
/* This code is contributed by Rajat Mishra*/
Python3
# A naive recursive implementation that
# simply follows the above optimal
# substructure property
import sys
# Matrix A[i] has dimension p[i-1] x p[i]
# for i = 1..n
def MatrixChainOrder(p, i, j):
if i == j:
return 0
_min = sys.maxsize
# place parenthesis at different places
# between first and last matrix,
# recursively calculate count of
# multiplications for each parenthesis
# placement and return the minimum count
for k in range(i, j):
count = (MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i-1] * p[k] * p[j])
if count < _min:
_min = count
# Return minimum count
return _min
# Driver code
arr = [1, 2, 3, 4, 3]
n = len(arr)
print("Minimum number of multiplications is ",
MatrixChainOrder(arr, 1, n-1))
# This code is contributed by Aryan Garg
C#
/* C# code for naive recursive implementation
that simply follows the above optimal
substructure property */
using System;
class GFG {
// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1..n
static int MatrixChainOrder(int[] p, int i, int j)
{
if (i == j)
return 0;
int min = int.MaxValue;
// place parenthesis at different places
// between first and last matrix, recursively
// calculate count of multiplications for each
// parenthesis placement and return the
// minimum count
for (int k = i; k < j; k++)
{
int count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver code
public static void Main()
{
int[] arr = new int[] { 1, 2, 3, 4, 3 };
int n = arr.Length;
Console.Write(
"Minimum number of multiplications is "
+ MatrixChainOrder(arr, 1, n - 1));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A naive recursive implementation
// that simply follows the above
// optimal substructure property
// Matrix Ai has dimension
// p[i-1] x p[i] for i = 1..n
function MatrixChainOrder(&$p, $i, $j)
{
if($i == $j)
return 0;
$min = PHP_INT_MAX;
// place parenthesis at different places
// between first and last matrix, recursively
// calculate count of multiplications for
// each parenthesis placement and return
// the minimum count
for ($k = $i; $k < $j; $k++)
{
$count = MatrixChainOrder($p, $i, $k) +
MatrixChainOrder($p, $k + 1, $j) +
$p[$i - 1] *
$p[$k] * $p[$j];
if ($count < $min)
$min = $count;
}
// Return minimum count
return $min;
}
// Driver Code
$arr = array(1, 2, 3, 4, 3);
$n = sizeof($arr);
echo "Minimum number of multiplications is " .
MatrixChainOrder($arr, 1, $n - 1);
// This code is contributed by ita_c
?>
Javascript
<script>
/* A naive recursive implementation that simply follows
the above optimal substructure property */
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
function MatrixChainOrder(p , i , j)
{
if (i == j)
return 0;
var min = Number.MAX_VALUE;
// place parenthesis at different places between
// first and last matrix, recursively calculate
// count of multiplications for each parenthesis
// placement and return the minimum count
var k=0;
for (k = i; k < j; k++)
{
var count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
// Driver code
var arr = [ 1, 2, 3, 4, 3 ];
var n = arr.length;
document.write(
"Minimum number of multiplications is "
+ MatrixChainOrder(arr, 1, n - 1));
// This code contributed by shikhasingrajput
</script>
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>
C++
// See the Cormen book for details of the
// following algorithm
#include <bits/stdc++.h>
using namespace std;
// Matrix Ai 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 m[][]. 0th row and 0th
column of m[][] are not used */
int m[n][n];
int i, j, k, L, q;
/* m[i, j] = Minimum number of scalar
multiplications needed to compute the
matrix A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying
// one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, size);
getchar();
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// See the Cormen book for details of the following
// algorithm
#include <limits.h>
#include <stdio.h>
// Matrix Ai 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 m[][].
0th row and 0th
column of m[][] are not used */
int m[n][n];
int i, j, k, L, q;
/* m[i, j] = Minimum number of
scalar multiplications
needed to compute the matrix
A[i]A[i+1]...A[j] =
A[i..j] where dimension of A[i]
is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L = 2; L < n; L++) {
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, size));
getchar();
return 0;
}
Java
// Dynamic Programming Java implementation of Matrix
// Chain Multiplication.
// See the Cormen book for details of the following
// algorithm
class MatrixChainMultiplication
{
// Matrix Ai 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 m[][]. 0th row
and 0th column of m[][] are not used */
int m[][] = new int[n][n];
int i, j, k, L, q;
/* m[i, j] = Minimum number of scalar
multiplications needed to compute the matrix
A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
if (j == n)
continue;
m[i][j] = Integer.MAX_VALUE;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[] { 1, 2, 3, 4 };
int size = arr.length;
System.out.println(
"Minimum number of multiplications is "
+ MatrixChainOrder(arr, size));
}
}
/* This code is contributed by Rajat Mishra*/
Python3
# Dynamic Programming Python implementation of Matrix
# Chain Multiplication. See the Cormen book for details
# of the following algorithm
import sys
maxint=int(1e9+7)
# Matrix Ai 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 m[][].
# 0th row and 0th
# column of m[][] are not used
m = [[0 for x in range(n)] for x in range(n)]
# m[i, j] = Minimum number of scalar
# multiplications needed
# to compute the matrix A[i]A[i + 1]...A[j] =
# A[i..j] where
# dimension of A[i] is p[i-1] x p[i]
# cost is zero when multiplying one matrix.
for i in range(1, n):
m[i][i] = 0
# L is chain length.
for L in range(2, n):
for i in range(1, n-L + 1):
j = i + L-1
m[i][j] = maxint
for k in range(i, j):
# q = cost / scalar multiplications
q = m[i][k] + m[k + 1][j] + p[i-1]*p[k]*p[j]
if q < m[i][j]:
m[i][j] = q
return m[1][n-1]
# Driver code
arr = [1, 2, 3, 4]
size = len(arr)
print("Minimum number of multiplications is " +
str(MatrixChainOrder(arr, size)))
# This Code is contributed by Bhavya Jain
C#
// Dynamic Programming C# implementation of
// Matrix Chain Multiplication.
// See the Cormen book for details of the
// following algorithm
using System;
class GFG
{
// Matrix Ai 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 m[][]. 0th row and 0th
column of m[][] are not used */
int[, ] m = new int[n, n];
int i, j, k, L, q;
/* m[i, j] = Minimum number of scalar
multiplications needed
to compute the matrix A[i]A[i+1]...A[j]
= A[i..j] where dimension of A[i] is
p[i-1] x p[i] */
// cost is zero when multiplying
// one matrix.
for (i = 1; i < n; i++)
m[i, i] = 0;
// L is chain length.
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
if (j == n)
continue;
m[i, j] = int.MaxValue;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i, k] + m[k + 1, j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i, j])
m[i, j] = q;
}
}
}
return m[1, n - 1];
}
// Driver code
public static void Main()
{
int[] arr = new int[] { 1, 2, 3, 4 };
int size = arr.Length;
Console.Write("Minimum number of "
+ "multiplications is "
+ MatrixChainOrder(arr, size));
}
}
// This code is contributed by Sam007
PHP
<?php
// Dynamic Programming Python implementation
// of Matrix Chain Multiplication.
// See the Cormen book for details of the
// following algorithm Matrix Ai 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 m[][]. 0th row and 0th
column of m[][] are not used */
$m[][] = array($n, $n);
/* m[i, j] = Minimum number of scalar
multiplications needed to compute the
matrix A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for ($i = 1; $i < $n; $i++)
$m[$i][$i] = 0;
// L is chain length.
for ($L = 2; $L < $n; $L++)
{
for ($i = 1; $i < $n - $L + 1; $i++)
{
$j = $i + $L - 1;
if($j == $n)
continue;
$m[$i][$j] = PHP_INT_MAX;
for ($k = $i; $k <= $j - 1; $k++)
{
// q = cost/scalar multiplications
$q = $m[$i][$k] + $m[$k + 1][$j] +
$p[$i - 1] * $p[$k] * $p[$j];
if ($q < $m[$i][$j])
$m[$i][$j] = $q;
}
}
}
return $m[1][$n-1];
}
// Driver Code
$arr = array(1, 2, 3, 4);
$size = sizeof($arr);
echo"Minimum number of multiplications is ".
MatrixChainOrder($arr, $size);
// This code is contributed by Mukul Singh
?>
Javascript
<script>
// Dynamic Programming javascript implementation of Matrix
// Chain Multiplication.
// See the Cormen book for details of the following
// algorithm
// Matrix Ai 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 m. 0th row
and 0th column of m are not used */
var m = Array(n).fill(0).map(x => Array(n).fill(0));
var i, j, k, L, q;
/* m[i, j] = Minimum number of scalar
multiplications needed to compute the matrix
A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
if (j == n)
continue;
m[i][j] = Number.MAX_VALUE;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
// Driver code
var arr = [ 1, 2, 3, 4 ];
var size = arr.length;
document.write(
"Minimum number of multiplications is "
+ MatrixChainOrder(arr, size));
// This code contributed by Princi Singh
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA