动态规划算法解决矩阵连乘问题：最优值表、路径表和计算过程

假设矩阵链乘的矩阵个数为n，矩阵链乘的矩阵维度保存在一个数组p中，其中矩阵Ai的维度为p[i-1] x p[i]。

首先，我们需要创建两个n x n的二维数组m和s，分别用来保存最优值和最优路径。

m[i][j]表示从矩阵Ai乘到矩阵Aj的最小乘法次数
s[i][j]表示从矩阵Ai乘到矩阵Aj的最优路径中，最后一个乘法的位置

初始化最优值表m和路径表s的对角线元素为0。

接下来，我们需要填充最优值表m和路径表s。我们使用一个变量k来表示当前计算的矩阵链长度，从2开始逐渐增加，直到n。对于每个k值，再从左上角开始，以k为步长逐渐向右下角填充表格。

具体的填充过程如下：

1. 对于每个长度为k的矩阵链，我们需要计算m[i][j]和s[i][j]，其中i表示矩阵链的起始位置，j表示矩阵链的结束位置。
2. 首先，我们需要计算i和j之间的最小乘法次数。假设k的取值范围为(i, j-1)，则最小乘法次数可以通过以下公式计算： m[i][j] = min{m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]}，其中i <= k < j。
3. 接下来，我们需要记录最优路径中最后一个乘法的位置。假设k的取值范围为(i, j-1)，则最后一个乘法的位置可以通过以下公式计算： s[i][j] = argmin{m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]}，其中i <= k < j。

最后，我们可以根据路径表s来构造最优路径。

下面是具体的计算过程：

假设矩阵链乘的矩阵个数为6，矩阵链乘的矩阵维度保存在数组p中。

p = [30, 35, 15, 5, 10, 20, 25]

首先，我们创建两个6 x 6的二维数组m和s，并将对角线元素初始化为0。

m = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

s = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

接下来，我们从长度为2的矩阵链开始填充最优值表m和路径表s。

当k=2时，我们需要计算m[i][j]和s[i][j]，其中i表示矩阵链的起始位置，j表示矩阵链的结束位置。

k=2:
m[1][2] = min{m[1][1] + m[2][2] + p[0] * p[1] * p[2]}
        = min{0 + 0 + 30 * 35 * 15}
        = 15750

s[1][2] = argmin{m[1][1] + m[2][2] + p[0] * p[1] * p[2]}
        = argmin{0 + 0 + 30 * 35 * 15}
        = 1

当k=3时，我们需要计算m[i][j]和s[i][j]。

k=3:
m[1][3] = min{m[1][1] + m[2][3] + p[0] * p[1] * p[3],
              m[1][2] + m[3][3] + p[0] * p[2] * p[3]}
        = min{0 + 0 + 30 * 35 * 5,
              15750 + 0 + 30 * 15 * 5}
        = 7875

s[1][3] = argmin{m[1][1] + m[2][3] + p[0] * p[1] * p[3],
                 m[1][2] + m[3][3] + p[0] * p[2] * p[3]}
        = argmin{0 + 0 + 30 * 35 * 5,
                 15750 + 0 + 30 * 15 * 5}
        = 1

当k=4时，我们需要计算m[i][j]和s[i][j]。

k=4:
m[1][4] = min{m[1][1] + m[2][4] + p[0] * p[1] * p[4],
              m[1][2] + m[3][4] + p[0] * p[2] * p[4],
              m[1][3] + m[4][4] + p[0] * p[3] * p[4]}
        = min{0 + 0 + 30 * 35 * 10,
              15750 + 0 + 30 * 15 * 10,
              7875 + 0 + 30 * 5 * 10}
        = 9725

s[1][4] = argmin{m[1][1] + m[2][4] + p[0] * p[1] * p[4],
                 m[1][2] + m[3][4] + p[0] * p[2] * p[4],
                 m[1][3] + m[4][4] + p[0] * p[3] * p[4]}
        = argmin{0 + 0 + 30 * 35 * 10,
                 15750 + 0 + 30 * 15 * 10,
                 7875 + 0 + 30 * 5 * 10}
        = 3

当k=5时，我们需要计算m[i][j]和s[i][j]。

k=5:
m[1][5] = min{m[1][1] + m[2][5] + p[0] * p[1] * p[5],
              m[1][2] + m[3][5] + p[0] * p[2] * p[5],
              m[1][3] + m[4][5] + p[0] * p[3] * p[5],
              m[1][4] + m[5][5] + p[0] * p[4] * p[5]}
        = min{0 + 0 + 30 * 35 * 20,
              15750 + 0 + 30 * 15 * 20,
              7875 + 0 + 30 * 5 * 20,
              9725 + 0 + 30 * 10 * 20}
        = 13300

s[1][5] = argmin{m[1][1] + m[2][5] + p[0] * p[1] * p[5],
                 m[1][2] + m[3][5] + p[0] * p[2] * p[5],
                 m[1][3] + m[4][5] + p[0] * p[3] * p[5],
                 m[1][4] + m[5][5] + p[0] * p[4] * p[5]}
        = argmin{0 + 0 + 30 * 35 * 20,
                 15750 + 0 + 30 * 15 * 20,
                 7875 + 0 + 30 * 5 * 20,
                 9725 + 0 + 30 * 10 * 20}
        = 1

当k=6时，我们需要计算m[i][j]和s[i][j]。

k=6:
m[1][6] = min{m[1][1] + m[2][6] + p[0] * p[1] * p[6],
              m[1][2] + m[3][6] + p[0] * p[2] * p[6],
              m[1][3] + m[4][6] + p[0] * p[3] * p[6],
              m[1][4] + m[5][6] + p[0] * p[4] * p[6],
              m[1][5] + m[6][6] + p[0] * p[5] * p[6]}
        = min{0 + 0 + 30 * 35 * 25,
              15750 + 0 + 30 * 15 * 25,
              7875 + 0 + 30 * 5 * 25,
              9725 + 0 + 30 * 10 * 25,
              13300 + 0 + 30 * 20 * 25}
        = 18300

s[1][6] = argmin{m[1][1] + m[2][6] + p[0] * p[1] * p[6],
                 m[1][2] + m[3][6] + p[0] * p[2] * p[6],
                 m[1][3] + m[4][6] + p[0] * p[3] * p[6],
                 m[1][4] + m[5][6] + p[0] * p[4] * p[6],
                 m[1][5] + m[6][6] + p[0] * p[5] * p[6]}
        = argmin{0 + 0 + 30 * 35 * 25,
                 15750 + 0 + 30 * 15 * 25,
                 7875 + 0 + 30 * 5 * 25,
                 9725 + 0 + 30 * 10 * 25,
                 13300 + 0 + 30 * 20 * 25}
        = 1

最后，我们可以根据路径表s来构造最优路径。假设起始位置为1，结束位置为6。

构造最优路径：
1. 如果s[1][6] = 1，则表示最优路径中最后一个乘法的位置为(1, 1)，即A1 * (A2 * (A3 * (A4 * (A5 * A6))))。
2. 如果s[1][6] = 2，则表示最优路径中最后一个乘法的位置为(2, 6)，即(A1 * A2) * (A3 * (A4 * (A5 * A6)))。
3. 如果s[1][6] = 3，则表示最优路径中最后一个乘法的位置为(2, 5)，即(A1 * A2) * ((A3 * A4) * (A5 * A6))。
4. 如果s[1][6] = 4，则表示最优路径中最后一个乘法的位置为(4, 6)，即(A1 * ((A2 * A3) * A4)) * (A5 * A6)。
5. 如果s[1][6] = 5，则表示最优路径中最后一个乘法的位置为(5, 6)，即((A1 * ((A2 * A3) * A4)) * A5) * A6)。

根据以上计算过程，得到最优值表m和路径表s如下：

m = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 15750, 7875, 9725, 13300],
    [0, 0, 0, 2625, 5375, 9425],
    [0, 0, 0, 0, 750, 2500],
    [0, 0, 0, 0, 0, 5000],
    [0, 0, 0, 0, 0, 0]
]

s = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 3, 3, 3],
    [0, 0, 0, 2, 3, 3],
    [0, 0, 0, 0, 4, 4],
    [0, 0, 0, 0, 0, 5],
    [0, 0, 0, 0, 0, 0]
]