Matrix-Chain Product，矩阵连乘问题

矩阵乘法支持结合律的（associative），比如计算ABC，可以(AB)C，也可以A(BC)。不同的计算顺序，结果一样，但是计算量却很不同。矩阵连乘问题，就是寻找最小计算量的计算方法。

比如有两个矩阵做乘法，\(A_{p,q}\cdot B_{q,r}=C_{p,r}\)，完成这个矩阵乘法，共计算了\(pqr\)次scale乘法。当有一串矩阵连乘时，\(A_1A_2...A_n\)，如何组合才能够让总的scale乘法量最小，这也是性能最好的矩阵乘法顺序。

输入是一个list，矩阵的dimension list，长度刚好比矩阵数量多1。

Subproblems

此问题不能使用In or Out的思路来构建子问题的递归，比如ABCD，A与B有两种可能，AB，或没有AB，当没有AB的时候，我们无法计算出A(的值，最右边的那个参数是缺失的。此时，只能使用Cut and Paste思路，将问题划分成左右两个subproblems，然后分别求解，最后再计算合并之后的值。

递归

一串矩阵连乘，可以考虑在中间任意一个位置划开，形成两串矩阵，这两串矩阵就是两个子问题。分别对这两个子问题递归，然后两串矩阵最后的解做最后的乘法，最后再选出计算量最小的那一个。代码如下：

def mcp(mc,i,j):
    if i == j-1:
        return 0
    lst = []
    for k in range(i+1,j):
        n = mcp(mc, i, k) \
                + mcp(mc, k, j) \
                + mc[i]*mc[k]*mc[j]
        lst.append(n)
    return min(lst)

Dynamic Programming

Top-Down

class MatrixChain():

    def __init__(self, dlst):
        self.dlst = dlst
        self.dd = {}

    def mcp(self, i, j):
        if (i,j) in self.dd:
            return self.dd[i,j]
        if i == j-1:
            return 0
        lst = []
        for k in range(i+1,j):
            n = self.mcp(i, k) \
                 + self.mcp(k, j) \
                 + self.dlst[i] * self.dlst[k] * self.dlst[j]
            lst.append(n)
        self.dd[i,j] = min(lst)
        return self.dd[i,j]

如果i和j是子问题最左边和最右边矩阵的编号，\(1\le i \le j\)，每一对i和j，都对应一个子问题。

Bottom-Up

def mcp_bu(mc):
    size = len(mc) - 1
    T = [[0]*size for _ in range(size)]
    for i in range(size-1):
        T[i][i+1] = mc[i] * mc[i+1] * mc[i+2]
    for d in range(2,size):
        for i in range(size-d):
            assert T[i][i+d-1] != 0
            assert T[i+1][i+d] != 0
            a = T[i][i+d-1] + mc[i]*mc[i+d]*mc[i+d+1]
            b = T[i+1][i+d] + mc[i]*mc[i+1]*mc[i+d+1]
            T[i][i+d] = min(a,b)
    return T[0][size-1]

1. AB, BC, CD, DE
2. 
(AB)C or A(BC),
(BC)D or B(CD),
(CD)E or C(DE),
3.
(ABC)D or A(BCD),
(BCD)E or B(CDE),
4.
(ABCD)E or A(BCDE)

如何加括号

到底要如何加括号才能实现最小计算量，代码中还要加点东西，记录下来每次抉择的位置信息。具体就是记录下来每一对i和j所对应的最优的k的位置，在整个计算完成之后，用这个信息把所有加括号的位置找出来。代码略。