华北电力大学实验报告实验名称：算法设计与分析实验课程名称：算法设计与程序分析专业班级：学生姓名：学号：2011成绩：指导教师：刘军实验日期：2013.11实验一矩阵连乘（动态规划）一、实验目的：掌握基本的动态规划思想，学习解决格路问题的基本思想。二、实验内容：给定n个矩阵A1,A2,，An，其中Ai与Ai+1是可乘的，i=l,2,，n-1。要算出这n个矩阵的连乘积AlA2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4）,（A1（A2A3）A4）
