import numpy as np


D= {}
def par_rec(L, i, j): 
    if (i, j) in D : 
        return D[i, j]
    elif i == j : 
        res = 0
    else : 
        min = L[i]*L[i+1]*L[j+1] + par_rec(L, i+1, j)
        for k in range(i+1, j): 
            gauche = par_rec(L, i, k)
            droite = par_rec(L, k+1, j)
            min_pot = gauche + droite + L[i]*L[k+1]*L[j+1]
            if min_pot<min : 
                min = min_pot
        res = min
        D[i, j] = res
    return res
    



def choix_parenthesage(L): 
    n = len(L)-1
    M = np.zeros((n, n))
    S = -np.ones((n, n))
    for d in range(1, n): 
        for i in range(0, n-d): 
            M[i, i+d] = M[i,i] + M[i+1, i+d] + L[i]*L[i+1]*L[i+d+1]
            S[i, i+d] = i
            for k in range(i, i+d): 
                m = M[i, k] + M[k+1, i+d] + L[i]*L[k+1]*L[i+d+1]
                if m<M[i, i+d]: 
                    M[i, i+d] = m
                    S[i, i+d] = i + k
    return S, M



def cout_cascade(L): 
    n = len(L) - 1
    res = 0
    for k in range(1, n) : 
        res = res + L[0]*L[k]*L[k+1]
    return res



L = [1200, 2000, 345, 560, 1000, 489]
S, M = choix_parenthesage(L)


def parenthese_opt(S, i, j): 
    if i == j : 
        return 'A' + str(i)
    elif j == i + 1 : 
        return 'A'+str(i) + 'A'+str(j)
    else : 
        k = S[i][j]
        G = parenthese_opt(S, i, k)
        D = parenthese_opt(S, k+1, j)
        if k > i : 
            G = '(' + G + ')'
        if j > k+1 : 
            D = '(' + D + ')'
        return G + D