编程实现5个矩阵连乘问题的备忘录算法

矩阵连乘问题的备忘录算法，也称为动态规划方法，用于优化计算两个矩阵A、B、C...等的乘积，避免重复计算已经计算过的中间结果。以下是基本的步骤：

1. 定义一个二维数组或哈希表（字典），`memo`，存储每个较小维度的结果。键通常是表示乘法过程的矩阵序列，值是对应的结果。

2. **函数递归**：
- 对于矩阵A * B * C，首先检查`memo[A][B]`是否已存在，如果存在则直接返回该值。
- 如果不存在，计算A * B并将其结果存储到`memo[A][B]`，然后用`memo[A][B]`去计算`memo[A][B] * C`。

3. **边界条件**：
- 矩阵乘法的基本操作是两个向量相乘，当遇到只有一维的矩阵时，不需要进一步计算，直接返回那个一维向量。

4. **效率提升**：
- 使用备忘录策略可以避免对相同子问题的多次计算，大大减少了时间复杂度。

以下是一个简单的Python示例代码：

def matrixMultiply(memo, A, B):
    if (A, B) in memo:
        return memo[(A, B)]
    
    if len(B[0]) == 1: # 如果B的最后一列只有1个元素，直接相加
        result = [sum(A[i] * row for i in range(len(A))) for row in B]
    else:
        result = [[sum(A[i][j] * B[j][k] for j in range(len(B[0]))) for k in range(len(B))] for i in range(len(A))]

    memo[(A, B)] = result
    return result

# 初始化空的备忘录
memo = {}

# 示例：计算矩阵A、B、C的连乘
matrix1 = [[1, 2], [3, 4]]
matrix2 = [[5, 6], [7, 8]]
matrix3 = [[9, 10], [11, 12]]

result = matrixMultiply(memo, matrix1, matrix2)
result = matrixMultiply(memo, result, matrix3)