#!usr/bin/python3
#-*- coding=utf-8 -*-

"""
动态规划思想：
    实质是分支思想和解决冗余，将待求解的问题分解为更小的、相同的子问题，然后对子问题求解，最终产生一个整体最优解。
    适合动态规划求解的问题，经分解得到的子问题往往不是相互独立的。空间换时间。
各个算法特点：
    贪心算法：
         当前选择坤宁要依赖于已经做出的选择，但不依赖于还未做出的选择和子问题，因此特点是自顶向下，一步步地做出贪心选择，
        但如果当前选择可能要依赖子问题的解时，就难以通过局部的贪心策略达到整体最优。
    分治法：
        分治法中各个子问题独立（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并
    成原问题的解。但如果各个子问题是不独立的，则分治法需要做很多不必要的工作，即重复地解公共的子问题，对时间消耗太大。
动态规划步骤：
    （1）分析最优解的性质，刻画最优解的结构特征——是否适合采用动态规划。
    （2）递归定义最优值（即建立递归式或动态规划方程）。
    （3）以自底向上的方式计算出最优值，并记录相关信息。
    （4）根据计算最优值时得到的信息，构造出最优解。
动态规划的基本要素：
    最优子结构性质、子问题重叠性质、自底向上的求解方法。
说明：
    矩阵连乘
    问题：
        给定n个矩阵{A1,A2,A3,````,An},其中Ai与A(i-1)（i=1,1,```,n-1）是可乘的。用加括号的方法表示矩阵连乘的次序，不同加
        括号的方法所对应的计算次序不同。


"""
import numpy as np
#求最优值并记录相关信息
def MatrixChain(p,n):
    #存储最优值
    m = np.zeros((n+1,n+1))     #牺牲第0行和第0列
    #存储最优决策
    s = np.zeros((n+1,n+1))
    #单个矩阵连乘的次数
    for i in range(n+1):
        m[i][i] = 0
        s[i][i] = 0
    #r表示子问题的规模，即连乘的矩阵的个数，从两个矩阵开始，规模逐步放大到n
    for r in range(2,n+1):
        #控制规模为r的子问题个数，共n-r+1个
        for i in range(1,n-r+2):
            j = i+r-1
            #计算第一种决策对应的乘法次数，从Aj处分开的决策
            m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]
            s[i][j] = 1
            #计算i+1处分开的决策、i+2处分开的决策、······直到j-1处的决策的乘法次数，取最小值及对应的决策
            for k in range(i+1,j):
                t = m[i][j] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if t < m[i][j]:
                    m[i][j] = t
                    s[i][j] = k
    return m,s

def Traceback(i,j,s):
    global res
    if i == j:
        res.append('A' + str(i))
    else:
        res.append('(')
        Traceback(i,int(s[i][j]),s)
        Traceback(int(s[i][j]+1),j,s)
        res.append(')')

if __name__=="__main__":
    arr = [[3,2],[2,5],[5,10],[10,2],[2,3]]
    n = len(arr)
    res = []
    #处理矩阵的行和列
    p = []
    for i in range(n):
        if i == 0:
            p.append(arr[0][0])
            p.append(arr[0][1])
        else:
            p.append(arr[i][1])
    m,s = MatrixChain(p,n)
    Traceback(1,n,s)
    print(''.join(res))