Algoritmo para enmarcar una expresión para maximizar su valor

Question

Lo encontré al buscar problemas en la programación dinámica. Se le ha dado una expresión sin sintetizar del formulario V0 O0 V1 O1 .... Vn-1

Tenemos que poner los paréntesis en los lugares que maximizan el valor de toda la expresión.

V's son los operandos y O son los operadores. En la primera versión del problema, los operadores pueden ser * y + y los operandos son positivos. La segunda versión del problema es completamente general.

Para la primera versión se me ocurrió la solución DP.

Solución - A [] = operandos array B [] - operadores array T (A [i, j]) - valor máximo de expresión T (A [0, n-1]) = max encima todo i {(T (A [0, i]) Oi T (A [i + 1, n-1]))}

Los casos límite son triviales (cuando i = j). Necesito ayuda con lo siguiente - Analice el tiempo de ejecución de este algoritmo. Y si existe uno mejor.

Answer 1

Es más fácil analizar el cálculo de los elementos A[i,j] de rangos más cortos a rangos más largos. Algoritmo para que se parece a:

# Initialization of single values 
for i in 0, ..., n-1: 
    A[i,i] = V[i] 

# Iterate through number of operation 
for d in 1, ..., n-1: 
    # Range start 
    for i in 0, ..., n-1-d: 
    j = i + d 
    A[i,j] = max(A[i,x] O_x A[x+1,j] for x in i, ..., j-1) 

print 'Result', A[0,n-1] 

Desde A[] se puede implementar con acceso constante de tiempo (matriz) que el algoritmo es O(n^3).