动态规划-矩阵链乘
问题描述
给定n个矩阵构成的一个链给定｛A1,A2,…,An｝,其中i=1，2，...,n.矩阵Ai的维数为pi-1*pi，如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
最优子结构
对乘积A1A2...An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算A1...Ak和Ak+1...An，然后再将这两部分的结果相乘。最优子结构如下：假设A1A2...An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1...Ak的加括号方式必定为A1...Ak的一个最优加括号，后缀子链同理。一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。状态转移方程
代码实现
参考：算法导论十五章--矩阵链乘法-http://blog.csdn.net/liuzhanchen1987/article/details/7835053
