Algorytm zamawiania wyrażenia w celu zmaksymalizowania jego wartości

Question

Znalazłem to podczas wyszukiwania problemów z programowaniem dynamicznym. Otrzymałeś niezrównane wyrażenie formy V0 O0 V1 O1 .... Vn-1

Musimy umieścić nawiasy w miejscach, które maksymalizują wartość całego wyrażenia.

V to operandy, a O to operatory. W pierwszej wersji problemu operatorzy mogą być * i +, a operandy są dodatnie. Druga wersja problemu jest całkowicie ogólna.

W pierwszej wersji znalazłem rozwiązanie DP.

Rozwiązanie - A [] = operandy Tablica B [] - operatorów Tablica T (A [i, j]) - maksymalna wartość ekspresji T (A [0, n-1]) = max ponad all i {(T (A [0, i]) Oi T (A [i + 1, n-1]))}

Przypadki graniczne są trywialne (gdy i = j). Potrzebuję pomocy w następujących sprawach: Przeanalizuj czas działania tego algorytmu. A jeśli istnieje lepszy.

Answer 1

Łatwiej jest analizować obliczenia elementów z krótszych zakresów do dłuższych zakresów. Algorytm, który wygląda tak:

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

Od A[] mogą być realizowane ze stałym dostępem do czasu (array) niż algorytmu jest O(n^3).