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