动态规划中矩阵乘法的最终产品？

Question

我正在使用动态规划来寻找乘法矩阵的最佳顺序。
计算正确的顺序后，如何计算这些矩阵的最终产品？
我的意思是例如我有这些矩阵：

m = [40,20,30,10,30]

最优乘法顺序为：

((A1(A2A3))A4)

如何使用这个最优括号来计算((A1(A2A3))A4)的最终结果？
（假设我的值为 A1 - An）

Answer 1

假设你有一个包含矩阵的字典，例如 matrices = {'A1': ..., 'A2': ...}，并且这些是 Numpy 数组，你可以修改字符串以包含 __matmul__ 运算符 @ 然后计算结果 eval:

import re
import numpy as np

matrices = {f'A{i}': np.random.randint(0, 10, size=(2, 2)) for i in range(1, 5)}

equation = '((A1(A2A3))A4)'
equation = re.sub('(?<=[0-9)])(?=[(A])', '@', equation)
result = eval(equation, {}, matrices)