矩阵链乘动态规划算法伪代码

矩阵链乘动态规划算法伪代码如下：

MATRIX-CHAIN-ORDER(p)
1. n = p.length - 1
2. let m[1..n, 1..n] and s[1..n-1, 2..n] be new tables
3. for i = 1 to n
4.     m[i, i] = 0
5. for l = 2 to n
6.     for i = 1 to n-l+1
7.         j = i + l - 1
8.         m[i, j] = ∞
9.         for k = i to j-1
10.            q = m[i, k] + m[k+1, j] + p[i-1]*p[k]*p[j]
11.            if q < m[i, j]
12.                m[i, j] = q
13.                s[i, j] = k
14. return m and s

其中，p是一个数组，表示矩阵链中每个矩阵的维度，m[i,j]表示从第i个矩阵到第j个矩阵的最小乘法代价，s[i,j]表示从第i个矩阵到第j个矩阵的最优括号方案中，第一个被乘的矩阵的下标。