# Como nÃ£o tinha restriÃ§Ãµes no enunciado da questÃ£o escolhi o python pela facilidade de trabalhar com strings na hora de por os parenteses xD
#codigo foi implementado na versão 2.7.13

import sys

def f(i,j):
    return str(i)+','+str(j)

def matrix_chain_order(p): 
    n = len(p)-1 
    m, s = {}, {} 
    for i in xrange(1, n+1):
        m[f(i, i)] = 0 
    for l in xrange(2, n+1): 
        for i in xrange(1, n-l+2):
            j = i+l-1
            m[f(i, j)] = sys.maxint 
            for k in xrange(i, j): 
                q = m[f(i, k)]+m[f(k+1, j)]+p[i-1]*p[k]*p[j] 
                if q<m[f(i, j)]:
                    m[f(i, j)] = q 
                    s[f(i, j)] = k 
    return m, s

def get_optimal_parens(s, i, j): #step 4 pag 377 livro Cormen
    res = ''
    if i == j:
        return "A"+str(j)
    else:
        res += "("
        res += get_optimal_parens(s, i, s[f(i, j)])
        res += get_optimal_parens(s, s[f(i, j)]+1, j)
        res +=  ")"
        return res

def main():
    p = [30,35,15,5,10,20,25]
    m, s = matrix_chain_order(p)
    print 'optimal operations number:', m[f(1, len(p)-1)]
    print 'optimal parens', get_optimal_parens(s, 1, len(p)-1)


