扫码获取 VIP 码
添加管理员微信获取 VIP 码
矩阵连乘问题（Matrix Chain Multiplication Problem）是算法设计与分析中的经典优化问题。给定n个矩阵构成的连乘序列A1、A2、……、An，由于矩阵乘法满足结合律，不同的加括号次序会导致不同的标量乘法计算次数。问题的目标是在所有可能的加括号方式中，找出使总标量乘法次数最少的那种次序，并给出最少计算次数。
在给出严格定义之前，需要先明确矩阵乘法的基本代价模型。设矩阵A的规模为p×q，矩阵B的规模为q×r，二者相乘得到规模为p×r的矩阵C。计算C的每一个元素需要q次标量乘法和q-1次标量加法，C共有p×r个元素，因此整次矩阵乘法共需p×q×r次标量乘法。这一代价模型是整个矩阵连乘问题的计算基础，也是软考命题人最常考察的起点。这里需要强调，标量乘法与标量加法虽然同属于基本运算，但在算法复杂度分析中通常只统计标量乘法的次数，因为乘法运算的代价远高于加法，这也是代价模型约定俗成的做法。
矩阵连乘问题的形式化定义可以表述为：给定n+1个正整数p0、p1、……、pn，其中矩阵Ai的规模为p(i-1)×pi，求最优的完全加括号方案，使得计算连乘积A1A2……An所需的标量乘法次数最少。完全加括号是指给矩阵连乘序列加上足够多的括号，使得每一种可能的计算次序都被唯一地确定下来。例如三个矩阵A1、A2、A3相乘，存在(A1A2)A3和A1(A2A3)两种不同的完全加括号方式。对于n个矩阵，不同的完全加括号方式共有卡特兰数C(n-1)种，其数量随n增大呈指数级增长，因此穷举所有加括号方式是不可行的。
动态规划正是为解决这类具有最优子结构性质的问题而设计的算法范式。动态规划（Dynamic Programming）这一术语由理查德·贝尔曼在二十世纪五十年代提出，其核心思想是将原问题分解为若干相互重叠的子问题，先求解子问题，再由子问题的解逐步构造出原问题的解。与分治法不同，动态规划所分解出的子问题并非相互独立，而是大量重叠，因此动态规划通过保存已求解子问题的结果来避免重复计算，用空间代价换取时间效率。矩阵连乘问题恰恰是体现动态规划思想的典型范例，也是软考软件设计师科目中算法设计题的高频考点。需要澄清的是，动态规划中的规划一词并非指预先制定计划，而是指通过填表这种系统化的方式组织子问题的求解顺序，理解这一点有助于把握算法的本质。
矩阵连乘问题具备最优子结构性质，这是能够应用动态规划的根本前提。最优子结构的含义是，原问题的最优解包含了其子问题的最优解。具体到矩阵连乘，若计算连乘积AiAi+1……Aj的最优加括号方案在某处断开为两部分，即在矩阵Ak与A(k+1)之间断开，那么分别计算前缀部分Ai……Ak和后缀部分A(k+1)……Aj的加括号方案也必然是最优的。
用反证法可以严格证明这一点。假设计算Ai……Aj的最优方案在某处断开，而其中前缀部分Ai……Ak采用了非最优的加括号方式，其计算次数并非最少。那么可以改用前缀部分的最优加括号方式来替换，从而得到整个连乘积更少的计算次数，这与原方案最优的假设相矛盾。因此，任何最优方案中的每一段子序列加括号方式都必然是最优的，最优子结构性质成立。这一性质使得我们可以把求解整个连乘积的问题，递归地归结为求解规模更小的子序列连乘问题。
最优子结构性质的意义还在于，它为递推式的建立提供了理论依据。既然原问题的最优解必然由子问题的最优解组合而成，我们就可以放心地定义m[i][j]这一状态，并尝试通过枚举断开位置k、组合两个子问题的最优值来推导m[i][j]，而不必担心遗漏某些非最优的子问题解反而能构成更优的整体解。这种由性质到递推式的逻辑链条，是动态规划问题求解的标准思考路径。
值得注意的是，最优子结构并非矩阵连乘问题所独有，但并非所有具备最优子结构的问题都适合用动态规划求解。贪心算法同样依赖最优子结构，但贪心算法要求每个子问题的最优解能通过局部贪心选择唯一确定，而矩阵连乘问题中，断开位置k的取值在i到j-1之间都有可能是最优的，无法通过贪心策略直接判定，因而必须穷举所有可能的断开位置并取最小值。这正是动态规划与贪心算法在本问题上的本质区别，也是软考命题人喜欢设置辨析题的切入点。
矩阵连乘问题的第二个关键性质是子问题重叠。若采用朴素的递归方法求解，直接按照定义递归地尝试每一种断开位置，那么同一个子问题会被反复计算多次。例如计算A1……A5时，子问题A2……A4既可能出现在前缀A1……A3与后缀A4A5的分解中，也可能出现在前缀A1A2与后缀A3……A5的分解中，同一子问题被多次递归调用，产生大量冗余计算。
由于每个规模为n的问题都要遍历n-1种断开方式，而每种断开方式又会引出两个更小的子问题，这种朴素递归的时间复杂度是指数级的，与穷举加括号方式无异。重叠子问题的存在，意味着这些重复计算是大量的、可被复用的，这正是动态规划引入记忆化或填表机制的直接动因。通过把每个子问题的最优值存储在一个二维表中，后续再遇到相同子问题时直接查表取值，从而将指数级的时间复杂度压缩为多项式级。这种以空间换时间的思想，是理解动态规划全部价值的钥匙。
需要进一步说明的是，子问题重叠与子问题独立是动态规划与分治法的分水岭。在归并排序、快速排序等分治算法中，各子问题彼此独立，不存在重复求解，因而无需存储中间结果；而在矩阵连乘这类动态规划问题中，子问题高度重叠，若不存储中间结果，同样的计算会被反复执行，效率急剧下降。理解这一区别，考生便能在面对新问题时快速判断应当采用分治还是动态规划，这是算法选型能力的重要组成部分。
设m[i][j]表示计算连乘积Ai……Aj所需的最少标量乘法次数，其中i≤j。当i等于j时，只有一个矩阵，无需任何乘法，因此m[i][i]等于0。当i小于j时，可以在任意位置k（i≤k 自底向上填表是求解这一递推式的标准实现方式。由于m[i][j]的求解依赖于链长更短、即j-i更小的子问题，因此应当按照链长递增的顺序依次求解。先令链长l从2开始逐渐增大到n，对于每一个固定的链长l，枚举起点i从1到n-l+1，计算终点j等于i加l减1，再对每个i和j遍历断开位置k，用递推式更新m[i][j]，同时用二维数组s[i][j]记录取得最优值时的断开位置k，以便最终重构出最优的加括号方案。这一填表过程是整个算法的核心，也是手工计算题必须熟练掌握的操作流程。 值得强调的是，m表与s表承担着不同的职责。m表只存储子问题的最优值，即最少标量乘法次数，它回答的是最优解是多少；s表则存储每个子问题取得最优值时所选取的断开位置，它回答的是最优解如何构造。二者缺一不可，若只保留m表，虽然能求出最少次数，却无法还原具体的加括号次序。这种用一张表记数值、一张表记决策的双表结构，是动态规划中处理构造型问题的通用技巧，掌握之后可以迁移到其他需要输出最优方案的动态规划题目中。 为了更直观地理解填表过程，可以观察m表在对角线方向上的填充规律。m表是一个上三角矩阵，主对角线上全是0，表示单个矩阵无需乘法。填表严格沿着对角线逐条向外推进：先填充紧贴主对角线的那条次对角线，对应链长为2的子问题；再填充下一条对角线，对应链长为3的子问题；如此逐层外推，直到最右上角的元素m[1][n]，它正是原问题的最优解。这种对角线式的推进方式，形象地体现了自底向上、按规模递增求解的次序要求，是记忆填表过程的一种有效辅助手段。理解这一规律后，考生便能在纸上快速还原填表流程，而无需死记循环变量的边界。 动态规划在实际实现中存在两种经典范式：自顶向下的备忘录法（带记忆的递归）和自底向上的填表法。备忘录法保持递归的调用结构不变，在递归进入某个子问题之前先检查该子问题是否已经求解过，若已求解则直接返回存储的结果，否则递归求解并将结果存入备忘录中。自底向上填表法则按照子问题规模从小到大的顺序，依次计算并填充表格，最终得到原问题的解。 两种方法在时间复杂度上同为O(n³)，空间复杂度同为O(n²)，但各有特点。备忘录法只计算实际需要的子问题，在子问题空间不是全部可达的情况下可能更省时，但递归调用会带来额外的函数调用栈开销，在n较大时可能面临栈溢出的风险。自底向上填表法则无需递归，用迭代循环实现，代码结构清晰，是软考教材和真题中采用的标准方法，也是考生应当熟练掌握的实现形式。 矩阵连乘动态规划算法的时间复杂度为O(n³)。具体分析如下：外层循环控制链长l，从2到n共n-1轮；中层循环枚举起点i，每一轮最多n次；内层循环枚举断开位置k，最多n次。三重循环的叠加导致总的计算量约为n³量级。空间
三、分类与应用：备忘录法与动态规划的关系，以及复杂度与适用边界
3.1 自顶向下备忘录法与自底向上填表法的对比
3.2 时间复杂度与空间复杂度分析
本篇完！