Programa de Python para la 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 colocamos entre paréntesis el producto 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 operations
    A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Claramente, el primer paréntesis requiere menos número de operaciones. Dada una array p[] que representa la string de arrays tal que la i-ésima array Ai es de dimensión p[i-1] xp[i]. Necesitamos escribir una función MatrixChainOrder() que devuelva el número mínimo de multiplicaciones necesarias para multiplicar la string.

  Input: p[] = {40, 20, 30, 10, 30}   
  Output: 26000  
  There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  (A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

  Input: p[] = {10, 20, 30, 40, 30} 
  Output: 30000 
  There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. 
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  ((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

  Input: p[] = {10, 20, 30}  
  Output: 6000  
  There are only two matrices of dimensions 10x20 and 20x30. So there 
  is only one way to multiply the matrices, cost of which is 10*20*30

La siguiente es una implementación recursiva que simplemente sigue la propiedad de subestructura óptima anterior. 

# 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 program to test above function
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

Minimum number of multiplications is  30

Solución de programación dinámica 

# Dynamic Programming Python implementation of Matrix
# Chain Multiplication. See the Cormen book for details
# of the following algorithm
import sys
 
# 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] = sys.maxsize
            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 program to test above function
arr = [1, 2, 3, 4, 3]
size = len(arr)
 
print("Minimum number of multiplications is " +
       str(MatrixChainOrder(arr, size)))
# This Code is contributed by Bhavya Jain

Minimum number of multiplications is 30

Consulte el artículo completo sobre Multiplicación de strings de arrays | DP-8 para más detalles!