矩阵链乘法示例

示例：给定的序列是 {4, 10, 3, 12, 20, 7}。矩阵的尺寸分别为 4 x 10、10 x 3、3 x 12、12 x 20、20 x 7。我们需要计算 M [i,j]，其中 0 ≤ i, j≤ 5。我们知道 M [i, i] = 0 对所有 i 都成立。

让我们继续处理从对角线开始的计算。我们计算 2 个矩阵相乘的最优解。

这里 P₀ 到 P₅ 是位置，M₁ 到 M₅ 是大小为 (p_i 到 p_i-1) 的矩阵。

根据序列，我们得到一个公式

在动态规划中，所有方法的初始化都由 '0' 完成。所以我们用 '0' 初始化。这将按对角线排序。

我们需要考虑所有的组合，但只考虑输出组合的最小值。

Calculation of Product of 2 matrices:
1. m (1,2) = m1  x m2
           = 4 x 10 x  10 x 3
           = 4 x 10 x 3 = 120
		   
2. m (2, 3) = m2 x m3
            = 10 x 3  x  3 x 12
            = 10 x 3 x 12 = 360
			
3. m (3, 4) = m3 x m4 
            = 3 x 12  x  12 x 20
            = 3 x 12 x 20 = 720
			
4. m (4,5) = m4 x m5
           = 12 x 20  x  20 x 7
           = 12 x 20 x 7 = 1680

• 我们将对角线元素初始化为 i, j 值相等，值为 '0'。
• 之后，第二个对角线被排序，我们得到与它对应的所有值。

现在，第三个对角线将以相同的方式解决。

现在是 3 个矩阵的乘积

M [1, 3] = M1 M2 M3

1. 有两种情况可以通过以下方式解决此乘法：( M₁ x M₂) + M₃，M₁+ (M₂x M₃)
2. 在解决了这两种情况后，我们选择输出最小的那一种。

M [1, 3] =264

比较两种输出，**264** 是两种情况中的最小值，所以我们将 **264** 插入表中，并选择 ( M₁ x M₂) + M₃ 这种组合来生成输出。

M [2, 4] = M2 M3 M4

1. 有两种情况可以通过以下方式解决此乘法：(M₂x M₃)+M₄，M₂+(M₃ x M₄)
2. 在解决了这两种情况后，我们选择输出最小的那一种。

M [2, 4] = 1320

比较两种输出，**1320** 是两种情况中的最小值，所以我们将 **1320** 插入表中，并选择 M₂+(M₃ x M₄) 这种组合来生成输出。

M [3, 5] = M3  M4  M5

1. 有两种情况可以通过以下方式解决此乘法：( M₃ x M₄) + M₅，M₃+ ( M₄xM₅)
2. 在解决了这两种情况后，我们选择输出最小的那一种。

M [3, 5] = 1140

比较两种输出，**1140** 是两种情况中的最小值，所以我们将 **1140** 插入表中，并选择 ( M₃ x M₄) + M₅ 这种组合来生成输出。

现在是 4 个矩阵的乘积

M [1, 4] = M1  M2 M3 M4

可以通过以下三种情况来解决此乘法

1. ( M₁ x M₂ x M₃) M₄
2. M₁ x(M₂ x M₃ x M₄)
3. (M₁ xM₂) x ( M₃ x M₄)

在解决了这些情况后，我们选择输出最小的那一种。

M [1, 4] =1080

比较不同情况的输出，'**1080**' 是最小输出，所以我们将 1080 插入表中，并选择 (M₁ xM₂) x (M₃ x M₄) 组合来生成输出。

M [2, 5] = M2 M3 M4 M5

可以通过以下三种情况来解决此乘法

1. (M₂ x M₃ x M₄)x M₅
2. M₂ x( M₃ x M₄ x M₅)
3. (M₂ x M₃)x ( M₄ x M₅)

在解决了这些情况后，我们选择输出最小的那一种。

M [2, 5] = 1350

比较不同情况的输出，'**1350**' 是最小输出，所以我们将 1350 插入表中，并选择 M₂ x( M₃ x M₄ xM₅) 组合来生成输出。

现在是 5 个矩阵的乘积

M [1, 5] = M1  M2 M3 M4 M5

可以通过以下五种情况来解决此乘法

1. (M₁ x M₂ xM₃ x M₄ )x M₅
2. M₁ x( M₂ xM₃ x M₄ xM₅)
3. (M₁ x M₂ xM₃)x M₄ xM₅
4. M₁ x M₂x(M₃ x M₄ xM₅)

在解决了这些情况后，我们选择输出最小的那一种。

M [1, 5] = 1344

比较不同情况的输出，'**1344**' 是最小输出，所以我们将 1344 插入表中，并选择 M₁ x M₂ x(M₃ x M₄ x M₅) 组合来生成输出。

最终输出是

步骤 3：计算最优成本：假设矩阵 A_i 的维度为 p_i-1x p_i，对于 i=1, 2, 3....n。输入是一个序列 (p₀,p₁,......p_n)，其中 [p] 的长度为 n+1。该过程使用一个辅助表 m [1....n, 1.....n] 来存储 m [i, j] 的成本，以及一个辅助表 s [1.....n, 1.....n]，用于记录在计算 m [i, j] 时哪个 k 值实现了最优成本。

算法首先为 i=1, 2, 3.....n 计算 m [i, j] ← 0，这是长度为 1 的链的最小成本。