递归解决方案

Created: November-22, 2018

矩阵链乘法是一个可以使用动态编程解决的优化问题。给定一系列矩阵，目标是找到最有效的方法来乘以这些矩阵。问题实际上不是执行乘法，而只是决定所涉及的矩阵乘法的顺序。

假设我们有两个矩阵 A 1 和 A 2 ，其维数为 m * n 和 p * q 。根据矩阵乘法的规则，我们知道，

当且仅当 n = **p 时，**我们可以乘以 A 1 和 A 2 。这意味着 A 1 的列数必须等于 A 2 的行数。 **** ****
如果满足第一个条件并且我们将 A 1 和 A 2 相乘，我们将得到一个新矩阵，我们称之为维数 m * q 的 A 3 。 **** ****
要乘以 A 1 和 A 2 ，我们需要进行一些缩放器乘法。我们需要执行的缩放器乘法的总数是（ m * n * q ）或（ m * p * q ）。
甲 1 * 阿 2 是不等于阿 2 * 阿 1 。

如果我们具有分别具有尺寸 m * n ， n * p 和 p * q 的三个矩阵 A 1 ， A 2 和 A 3 ，那么 A 4 = A 1 * A 2 * A 3 将具有 m * q 的尺寸。现在我们可以通过两种方式执行此矩阵乘法： **** **** **** **** **** **** **** ****

首先，我们将 A 1 和 A 2 相乘，然后将结果乘以 A 3 。即：（ A 1 * A 2 ）* A 3 。
首先，我们将 A 2 和 A 3 相乘，然后将结果乘以 A 1 。即： 甲 1 *（ 阿 2 * 阿 3 ）。

你可以注意到乘法的顺序保持不变，即我们不会乘以（ A 1 * A 3 ）* A 2， 因为它可能无效。我们只更改括号以在将其与剩余值相乘之前将其相乘。我们如何放置这些括号是很重要的。为什么？比方说，的 3 维矩阵阿 1 ，阿 2 和阿 3 是 10 * 100 ， 100 * 5 ， 5 * 50 。然后，

对于（ A 1 * A 2 ）* A 3 ，缩放器乘法的总数是：（ 10 * 100 * 5 ）+（ 10 * 5 * 50 ）= 7500 次。
对于 A 1 *（ A 2 * A 3 ），缩放器乘法的总数是：（ 100 * 5 * 50 ）+（ 10 * 100 * 50 ）= 75000 次。

对于第 2 种类型，缩放器乘法的数量是第 1 种类型的 10 倍！因此，如果你能够找到一种方法来找出最小化总缩放器乘法所需的正确的括号方向，那么它将减少矩阵乘法所需的时间和内存。这就是矩阵链乘法派上用场的地方。在这里，我们不会关注矩阵的实际乘法，我们只会找出正确的括号顺序，以便缩放器乘法的数量最小化。我们将有矩阵 A 1 ， A 2 ， A 3 …….. A n 我们将找出乘以这些所需的最小缩放器乘法数。我们假设给定的维度是有效的，即它满足我们对矩阵乘法的第一个要求。

我们将使用分而治之的方法来解决这个问题。由于常见的子问题，需要动态编程。例如：对于 n = 5 ，我们有 5 个矩阵 A 1 ， A 2 ， A 3 ， A 4 和 A 5 。我们想要找出执行此矩阵乘法所需的最小乘法次数 A 1 * A 2 * A 3 * A 4 * A 5 。在很多方面，让我们专注于一个方面:( A. 1 * A 2 ）*（ A 3 * A 4 * A 5 ）。

对于这个，我们将发现 A left = A 1 * A 2 。阿右 = 阿 3 * 甲 4 * 甲 5 。然后，我们会发现一个答案 = 一个左 * 一个向右 。找出所需的缩放乘法总数一个答案 ：=确定需要缩放乘法的总数一左 +以确定所需的总人数定标器的乘法一个正确的 +确定 A 左 * A 右 所需的缩放器乘法总数。

最后一项，以确定需要缩放乘法的总数一左 * 一个右 行数：可以写成一个左 *列的数一离开 *在列数一个合适的 。（根据矩阵乘法的第 2 条规则）

但我们也可以用其他方式设置括号。例如：

甲 1 *（ 阿 2 * 阿 3 * 甲 4 * 甲 5 ）
（ A 1 * A 2 * A 3 ）*（ A 4 * A 5 ）
（ A 1 * A 2 * A 3 * A 4 ）* A 5 等

对于每种可能的情况，我们将确定找到 A 左 和 A 右 所需的缩放器乘法数，然后确定 A 左 * A 右 。如果你对递归有一个大致的了解，那么你已经了解了如何执行此任务。我们的算法将是：

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

为什么这是动态编程问题？要确定（ A 1 * A 2 * A 3 ），如果你已经计算过（ A 1 * A 2 ），那么在这种情况下它会有所帮助。

为了确定这种递归的状态，我们可以看到为了解决每种情况，我们需要知道我们正在使用的矩阵范围。所以我们需要一个开始和结束。当我们使用分而治之时，我们的基本情况将少于 2 个矩阵（开始 > = 结束），我们根本不需要乘法。我们将有 2 个数组：行和列。 row [i] 和 column [i] 将存储矩阵 A i 的行数和列数。我们将有一个 dp [n] [n] 数组来存储已经计算的值并用它初始化它 -1 ，其中 -1 表示尚未计算的值。 dp [i] [j] 表示乘以 A i ， A i + 1 ，…..， A j 所需的缩放器乘法的数量。伪代码看起来像：

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

复杂：

begin 和 end 的值可以是 1 到 n 。有 n 2 种不同的状态。对于每个状态，内部循环将运行 n 次。总时间复杂度：O(n³) 和内存复杂度：O(n²)。