矩阵连乘问题 R 解决方案2：动态规划法 应用动态规划，首先应分析问题的最优解结构特征 $将矩阵连乘积(AA+1A)简记为A[ij] Φ考察计算A[1:n]的最优计算次序： 设最优计算次序在Ak和Ak+1之间将矩阵链断开（1≤k<n) 则相应的完全加括号方式为：(A1…Ak)(Ak+1.An) 总计算量为如下三部分计算量之和： 求解A[1:k]的计算量 求解A[k+1:n]的计算量 求解A[1:k]和A[k+1:n]相乘的计算量矩阵连乘问题  解决方案2：动态规划法  应用动态规划，首先应分析问题的最优解结构特征  将矩阵连乘积 (Ai Ai+1 … Aj) 简记为A[i:j]  考察计算A[1:n]的最优计算次序： • 设最优计算次序在Ak和Ak+1之间将矩阵链断开（1≤k<n） • 则相应的完全加括号方式为： (A1 … Ak ) (Ak+1 … An ) • 总计算量为如下三部分计算量之和： – 求解A[1:k]的计算量 – 求解A[k+1:n]的计算量 – 求解A[1:k]和A[k+1:n]相乘的计算量