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

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)