矩阵链的乘法

1.问题
矩阵链的乘法
2.解析

1)最优加全部括号的结构
动态规划第一步是寻找一个最优的子结构。假设现在要计算AiAi+1…Aj的值,计算Ai…j过程当中肯定会存在某个k值(i<=k<j)将Ai…j分成两部分,使得Ai…j的计算量最小。分成两个子问题Ai…k和Ak+1…j,需要继续递归寻找这两个子问题的最优解。最优子结构为:假设AiAi+1…Aj的一个最优加全括号把乘积在Ak和Ak+1之间分开,则Ai…k和Ak+1…j也都是最优加全括号的。
2)一个递归解
  设m[i,j]为计算机矩阵Ai…j所需的标量乘法运算次数的最小值,对此计算A1…n的最小代价就是m[1,n]。现在需要来递归定义m[i,j],分两种情况进行讨论如下:
当i==j时:m[i,j] = 0,(此时只包含一个矩阵)
当i<j 时:从步骤1中需要寻找一个k(i≤k<j)值,使得m[i,j] =min{m[i,k]+m[k+1,j]+pi-1pkpj} (i≤k<j)。

3.设计
矩阵链的乘法
4.分析
时间复杂度:
矩阵链的乘法
5.源码
https://github.com/ylx1234/RecurMatrixChain