Algoritmo per raggruppare un'espressione per massimizzarne il valore

Question

L'ho trovato mentre cercavo problemi nella programmazione dinamica. Viene visualizzata un'espressione non filtrata del modulo V0 O0 V1 O1 .... Vn-1

Dobbiamo mettere parentesi nei punti che massimizzano il valore dell'intera espressione.

V sono gli operandi e O sono gli operatori. Nella prima versione del problema, gli operatori possono essere * e + e gli operandi sono positivi. La seconda versione del problema è completamente generale.

Per la prima versione mi sono imbattuto in soluzione DP.

Soluzione - A [] = operandi matrice B [] - operatori matrice T (A [i, j]) - valore massimo dell'espressione T (A [0, n-1]) = max oltre all i {(T (A [0, i]) Oi T (A [i + 1, n-1]))

I casi limite sono banali (quando i = j). Ho bisogno di aiuto con il seguente - Analizzare il tempo di esecuzione di questo algoritmo. E se ne esiste uno migliore.

Answer 1

È più semplice analizzare il calcolo degli elementi A[i,j] da intervalli più brevi a intervalli più lunghi. Algoritmo per che assomiglia:

# 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] 

Da A[] può essere implementato con accesso costante di tempo (array) di algoritmo è O(n^3).