算法分析与设计 矩阵链乘法之动态规划
算法分析与设计
矩阵链乘法之动态规划
问题描述：
给定n个矩阵的链<A 1 ,A 2 ,…,A n >，其中i=1,2,…,n，矩阵A i的维数为p i-1 ×p i 。求一个完全“括号化方案”，使得计算乘积A1 A2 …A n 所需的标量乘法次数最小。
算法思路：
假设矩阵Ai的维数是Pi-1*Pi，输入是一个序列P=<P0,P1,…,Pn>，其中length[p]=n+1.程序使用一个辅助表m[1…n,1…n]来保存m[i,j]的代价，用一个辅助表s[1…n,1…n]来记录m[i,j]取得最优代价时k的值。最后利用s构造最优解。
核心代码：
时间复杂度：
算法的时间复杂度为O(n^3)。
源码：
https://github.com/SpiritDemon-max/myText/blob/master/matrix_chain_order.cpp