Multiplicación de strings de arrays | DP-8

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *