给定一系列矩阵，找出计算这些矩阵乘积的最有效的算法。

因为矩阵乘法具有结合率，所以无论计算顺序如何，最后的结果一定是一样的。例如有 A，B，C，D 四个矩阵相乘：

ABCD = A(BCD) = (AB)(CD) = (ABC)D = ...

但是其括号乘积的顺序会影响到需计算乘积所需简单算术运算的数目，即其效率。例如A为10×30矩阵，B为30×5矩阵，C为5×60矩阵，则

(AB)C 有 10 × 30 × 5 + 10 × 5 × 60 = 4500 次运算

A(BC) 有 10 × 30 × 60 + 30 × 5 × 60 = 27000 次运算

所以，找出最有效率的算法，能够帮助我们节省很多的运算时间。

假设我们有4个矩阵，维度分别是[2, 3], [3, 6], [6, 4], [4, 5]，下面给出分析步骤。

我们先画出初始表格如下

| 矩阵 | 0 | 1 | 2 | 3 | | -------- | ---- | ---- | ---- | ---- | ---- | | 0 | 0 | | | | | 1 | | 0 | | | | 2 | | | 0 | | | 3 | | | | 0 |

  因为矩阵自己不能和自己相乘，所以在对角线上，给出了0的初始结果。

接下来，如果假设每次只能选择两个矩阵进行乘法计算，进一步得出图表如下。

| 矩阵 | 0 | 1 | 2 | 3 | | -------- | ---- | ---- | ---- | ---- | ---- | | 0 | 0 | 2×3×6=36 | | | | 1 | | 0 | 3×6×4=72 | | | 2 | | | 0 | 6×4×5=132 | | 3 | | | | 0 |

  这里其实很好理解，就是找临近的矩阵相乘，找出计算其乘法需要的计算次数。

然后，把矩阵扩大的3个，也就是找出其中的3个进行乘法计算，得出图表如下

| 矩阵 | 0 | 1 | 2 | 3 | | -------- | ---- | ---- | ---- | ---- | ---- | | 0 | 0 | 36 | 84 | | | 1 | | 0 | 72 | 132 | | 2 | | | 0 | 132 | | 3 | | | | 0 |

  从这4个矩阵中取3个，要么是取012，要么是123。
  
  1. 如果是012，组合可以是(01)2或者0(12)，取这两者中最小的结果。min(36 + 2 × 6 × 4, 2 × 3 × 4 + 72) = 84
  
  2. 如果是123，组合可以是(12)3或者1(23)，取这两者中最小的结果。min(72 + 3 × 4 × 5, 3 × 6 × 5 + 120) = 132

最后，把矩阵扩大到4个，得出图表如下

| 矩阵 | 0 | 1 | 2 | 3 | | -------- | ---- | ---- | ---- | ---- | ---- | | 0 | 0 | 36 | 84 | 124 | | 1 | | 0 | 72 | 132 | | 2 | | | 0 | 132 | | 3 | | | | 0 |

  1. 组合可以是(012)3，此时结果是 84 + 2 × 4 × 5 = 124
  
  2. 组合可以是(01)(23)，此时结果是 36 + 120 + 2 × 6 × 5 = 216
  
  3. 组合可以是0(123)，此时结果是 2 × 3 × 5 + 120 = 150
  
  这3个结果的最小值是124，所以得到结果124

# -*- coding: utf-8 -*- 


class Solution():
    def do(self, arr_matrix):
        '''
        鉴于矩阵的乘法必须遵循的性质，所以输入这里做了简化。
        arr_matrix[0], arr_matrix[1] 代表第一个矩阵的维度
        arr_matrix[1], arr_matrix[2] 代表第二个矩阵的维度
        依次类推
        '''
        len_matrix = len(arr_matrix) - 1
        dp = [[0] * len_matrix for _ in range(len_matrix)]
        for i in range(1, len_matrix):
            for j in range(len_matrix):
                if j + i >= len_matrix:
                    break
                dp[j][j + i] = 100000000000
                k = j + 1
                while k <= i + j:
                    temp = arr_matrix[j] * arr_matrix[k] * arr_matrix[j + i + 1] + \
                            dp[j][k - 1] + \
                            dp[k][i + j]
                    if temp < dp[j][j + i]:
                        dp[j][j + i] = temp
                    k += 1

        return dp[0][-1]

solution = Solution()
print solution.do([2,3,6,4,5])