用加泰罗尼亚数计算矩阵链乘法
Calculating matrix chain mutlipication with Catalan numbers
我研究了矩阵链乘法问题，并且了解该算法的作用。最近，我遇到了加泰罗尼亚数字，在解决 parenthesization problem 时派上了用场。这个问题在我看来与矩阵链乘法非常相似。事实上，在 CLRS 中，他们在矩阵链乘法章节中提到了加泰罗尼亚数。
我很好奇你能用加泰罗尼亚数算法解决矩阵链乘法吗？我的想法是：不，你无法解决，因为加泰罗尼亚数字描述了括号矩阵的方法数量，而最初的矩阵链问题提出了一个不同的问题——安排括号的特定方法会给出最小的成本。
我的想法正确吗？
矩阵链乘法和括号问题是等价的。一个可以简化为另一个。
链式矩阵乘法问题
给定一系列 n 个矩阵 A1, A2, ... An，它们的维度 p0, p1, p2, ..., pn，其中 i = 1, 2, ..., n，矩阵 Ai 的维度 pi − 1 × pi, 确定最小化标量乘法次数的乘法顺序。
等价形式：括号问题
给定n矩阵，A1, A2, ... An，其中1 ≤ i ≤ n，Ai是一个pi − 1 × pi矩阵，括号中的乘积A1, A2, ... An为了最小化总成本，假设使用朴素算法将 pi − 1× pi 矩阵乘以 pi × pi + 1 矩阵的成本为 pi − 1× pi × pi + 1
当你尝试写出上述问题的循环关系时，结果发现它与加泰罗尼亚数字的循环关系相同。因此catalan数可以用来解决矩阵链乘法问题
我研究了矩阵链乘法问题，并且了解该算法的作用。最近，我遇到了加泰罗尼亚数字，在解决 parenthesization problem 时派上了用场。这个问题在我看来与矩阵链乘法非常相似。事实上，在 CLRS 中，他们在矩阵链乘法章节中提到了加泰罗尼亚数。
我很好奇你能用加泰罗尼亚数算法解决矩阵链乘法吗？我的想法是：不，你无法解决，因为加泰罗尼亚数字描述了括号矩阵的方法数量，而最初的矩阵链问题提出了一个不同的问题——安排括号的特定方法会给出最小的成本。
我的想法正确吗？
矩阵链乘法和括号问题是等价的。一个可以简化为另一个。
链式矩阵乘法问题
给定一系列 n 个矩阵 A1, A2, ... An，它们的维度 p0, p1, p2, ..., pn，其中 i = 1, 2, ..., n，矩阵 Ai 的维度 pi − 1 × pi, 确定最小化标量乘法次数的乘法顺序。
等价形式：括号问题
给定n矩阵，A1, A2, ... An，其中1 ≤ i ≤ n，Ai是一个pi − 1 × pi矩阵，括号中的乘积A1, A2, ... An为了最小化总成本，假设使用朴素算法将 pi − 1× pi 矩阵乘以 pi × pi + 1 矩阵的成本为 pi − 1× pi × pi + 1
当你尝试写出上述问题的循环关系时，结果发现它与加泰罗尼亚数字的循环关系相同。因此catalan数可以用来解决矩阵链乘法问题