矩阵链乘法
矩阵链乘法（Matrix Chain Multiplication）是动态规划的经典问题。
问题描述
矩阵乘法具有结合律，不同的结合方式代价不同。对于一个 m×k 的矩阵与一个 k×n 的矩阵相乘，代价为 m×k×n。对于一串矩阵相乘的序列，目标是找到一种计算顺序使得总代价最小。
穷举局限性
解空间是指数级的，对于较大的 n，正常穷举是不可能的。
优化解结构
一个优化解必定是以某个分界点 k 为界，左右两部分的优化解的矩阵乘积。
代价传递方程
自下向上计算
先计算 m[1,1]、m[2,2] 等最小子问题，接着计算 m[1,2]、m[2,3] 等，不断向上直到计算出 m[1,n]。
算法实现
算法分析
时间复杂度 O(n³)，空间复杂度 O(n²)。
链接到
- 上一个知识点：2.1 动态规划原理
- 下一个知识点：2.3 最长公共子序列