括弧を入れて式を最大化する動的プログラミングソリューション

Question

私はAlgorithmic Toolbox course on Courseraから5 + 8 * 4-2のような算術式をとり、可能な限り大きな値を計算するアルゴリズムを実装しようとしています。しかし、私は実際のアルゴリズムの最後の部分でインデックスの選択を理解していません。私の実装では、2つのテーブル（サブ表現の最大値と最小値を格納するのに使われる）で初期化された値を使って値を計算することができません。

evalt関数は単に、チャーをとるオペランドにそれをオンにし、二桁の積を計算する：

def evalt(a, b, op): 
    if op == '+': 
     return a + b 
#and so on 

のMinMaxは最小と部分式

def MinMax(i, j, op, m, M): 
    mmin = 10000 
    mmax = -10000 
    for k in range(i, j-1): 
     a = evalt(M[i][k], M[k+1][j], op[k]) 
     b = evalt(M[i][k], m[k+1][j], op[k]) 
     c = evalt(m[i][k], M[k+1][j], op[k]) 
     d = evalt(m[i][k], m[k+1][j], op[k]) 
     mmin = min(mmin, a, b, c, d) 
     mmax = max(mmax, a, b, c, d) 
    return(mmin, mmax) 

の最大値を計算し、これは主な機能の本体です

def get_maximum_value(dataset): 
    op = dataset[1:len(dataset):2] 
    d = dataset[0:len(dataset)+1:2] 
    n = len(d) 
    #iniitializing matrices/tables 
    m = [[0 for i in range(n)] for j in range(n)] #minimized values 
    M = [[0 for i in range(n)] for j in range(n)] #maximized values 
    for i in range(n): 
     m[i][i] = int(d[i]) #so that the tables will look like 
     M[i][i] = int(d[i]) #[[i, 0, 0...], [0, i, 0...], [0, 0, i,...]] 
    for s in range(n): #here's where I get confused 
     for i in range(n-s): 
      j = i + s 
      m[i][j], M[i][j] = MinMax(i,j,op,m,M) 
    return M[0][n-1] 

Answer 1

大変申し訳ございませんが、ここには何がありますか改善されなければならなかった。主な機能で

for s in range(1,n) 

、とのMinMax機能で

for k in range(i, j): 

。今それは動作します。