动态规划---------矩阵连乘
一、动态规划
动态规划和分治法十分相似，动态规划的基本思想是将待求解的问题分解为若干子问题的解得到原问题的解。动态规划算法通常适用于求解最优化问题。
动态规划的步骤如下：
1、找出最优解的性质，并刻画其结构特征。
2、递归地定义最优值。
3、以自底向上的方式计算最优值。
4、根据计算的最优值时得到的信息，构造最优解。
二、矩阵连乘问题
问题描述：给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
思路：矩阵连乘可以通过添加括号来改变矩阵相乘时候的顺序，从而改变最终相乘的次数，所以我们只需要找到最优的添加括号的方式就能求出矩阵相乘时次数最少的那次。利用的是自底向上的方式。
对于两个矩阵相乘A1*A2，A1为p✖q矩阵，A2为q✖r矩阵，（两个矩阵可以相乘必须满足第一个矩阵的列数等于第二个矩阵的行数），两者相乘共需要p✖q✖r次。
我们将矩阵连乘Ai*Ai+1…*Aj，简记为A[i:j],所以我们需要求得就是A[i:n]的最优计算次序；假设矩阵A[i:j]（1
