本文共 703 字，大约阅读时间需要 2 分钟。
这一课介绍的矩阵链乘问题，是区间类型动态规划的典型例子，区间类型的动态规划是在线性动态规划基础上的扩展。我的理解是，这个扩展就是将固定的线性问题变成一个变长的线性问题，也就是说，所谓的区间动态规划，就是在一个可选择的线性区间中寻找某种最优的结果，而线性区间长度本身也是可变化的，最优结果的组合也是可变化的，需要在两重变化中寻找最优解。除了矩阵链乘问题，此类问题的典型例子还有石子合并问题、能量项链问题、最优排序二叉树问题等。除此之外，前几年非常火的多边形三角剖分问题，也被归纳为区间动态规划类型的题目。
《算法导论》一书在介绍动态规划问题时，举了一个矩阵链乘（Matrix-chain Multiplication）的例子。我知道很多读者害怕公式，看见《矩阵论》就头疼，但是不要怕，这个题目只涉及了一个简单的概念，就是矩阵的相容性（Compatible）。矩阵 A 和 B 能够相乘，前提是矩阵 A 和矩阵 B 必须相容，所谓的相容，就是矩阵 A 的列数等于矩阵 B 的行数。假设矩阵 A 是 $p\times q$ 的矩阵，矩阵 B 是 $q\times r$ 的矩阵，则矩阵 A 和矩阵 B 的乘积是一个 $p \times r$ 的矩阵。计算这个乘积需要 $p\times q\times r$ 次标量乘法计算和若干次加法，其计算量的主要代价就是这 $p\times q\times r$ 次乘法计算。
对于一组满足相容性条件（顺序）排列的矩阵做链乘，无论选择中间哪两个矩阵先计算，其结果都能与剩下的矩阵继续保持相容性条件，这是一个很重要的前提，因为调整矩阵的位置会破坏相容性。但是，在矩阵
转载地址：http://xdcgj.baihongyu.com/