Решение динамического программирования для максимизации выражения путем размещения круглых скобок

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) 

в основной функции, а

for k in range(i, j): 

в функции MinMax. Теперь это работает.