値を最大にするために式をかっこで括るアルゴリズム

Question

動的プログラミングの問題を調べている間にこれを見つけました。 V0 O0 V1 O1 .... Vn-1

式全体の値を最大にする場所に角カッコを入れる必要があります。

Vはオペランドであり、Oは演算子です。 問題の最初のバージョンでは、演算子は*および+となり、オペランドは正の数になります。 問題の第2版は完全に一般的です。

最初のバージョンでは、私はDPソリューションを思いついた。

ソリューション - A [] =オペランドアレイ B [] - オペレーター配列 T（[I、J]） - 式 Tの最大値（[0、N-1]）= maxの上をすべてのi {（T（A [0、i]）Oi T（A [i + 1、n-1]））}

境界ケースは簡単です（i = jの場合）。 私は以下のことについて助けが必要です。 このアルゴリズムの実行時間を分析します。そして、より良いものがあれば。

Answer 1

A[i,j]要素の計算を、より短い範囲からより長い範囲に分析する方が簡単です。アルゴリズムはO(n^3)あるより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] 

：そのためのアルゴリズムは次のようになります。