文档介绍：实验02动态规划算法
［实验目的］
掌握动态规划算法的基本方法
掌握动态规划算法中最优子结构的分析
掌握递归求解最优值的方法
掌握最优解的构造．
[预****要求］
认真阅读算法设计教材,了解动态规划原理；
设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的jａｖa程序.
[实验题］
给定n个矩阵{A１， Ａ2, …，Ａn}，其中,Ai与Ai＋１是可乘的,计算这n个矩阵的连乘积。从中找出一种乘次数最少的计算次序。
给定２个序列Ｘ=｛x１,x2,…,ｘm｝和Y={y1，ｙ２,…,yｎ}，找出Ｘ和Y的最长公共子序列．
在一块电路板的上、下２端分别有ｎ个接线柱．根据电路设计，要求用导线（i，π(ｉ）)将上端接线柱与下端接线柱相连,确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Ｎｅtｓ＝{（i，π（i)）,1≤i≤ｎ｝的最大不相交子集。
［实验步骤]
设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;
应用设计的算法和程序求解问题;
将程序整理成功能模块存盘备用.
[实验报告要求］
阐述实验目的和实验内容；
阐述求解问题的算法原理;
提交实验程序的功能模块；
记录最终测试数据和测试结果.
［参考]
1。／／矩阵连乘类
ｐuｂlic cｌａss Mａｔriｘ ｛
ﻩpｒｉｖａte ｉnt ＭＮ;ﻩﻩﻩ//表示矩阵链中矩阵的数目
ｐrｉvate iｎt［］ ｐ; ﻩ／/存放各个矩阵的维数
ﻩprｉｖate ｉｎt [][］［]Ａ;ﻩ／/存放要进行连乘的多个矩阵
ｐrivaｔe int ［］［]ｍ;ﻩﻩ／/用来存放Ａi到Ａj的最少乘次数
pｒivaｔe int ［］[］s；ﻩﻩ//用来存放Ai到Aj的最后断开位置
ﻩ//
ﻩpuｂlic Ｍaｔｒix(）
ﻩ{
ﻩﻩMN=0；
ﻩﻩp＝nｅw ｉｎt [ＭＮ］；
ﻩ}
ﻩ／/构造函数,L为矩阵的数目
ﻩpublic Mａｔｒix（iｎｔ Ｌ）
ﻩ｛
ﻩﻩMＮ=Ｌ；
ﻩﻩp=nｅｗ inｔ ［MN+1];
ﻩ A=ｎew ｉｎｔ [ＭN]［］［];
ﻩﻩm=ｎeｗ iｎｔ ［ＭN＋1］［MＮ+1]；
ﻩ s＝new ｉｎt [MＮ+１］[MＮ+1］；
ﻩ／／随机生成连乘矩阵的维数[1—11]
ﻩﻩｆor（ｉnt ｉ=0；ｉ<=ＭＮ；i＋+）
ﻩﻩ｛
ﻩﻩﻩp[i］＝（iｎt) Mａth．ｒound(Math。raｎdom()*1０）＋1;
ﻩﻩ}
ﻩﻩ/／随机生成各个矩阵
ﻩfoｒ(inｔ i＝0；ｉ〈MN；i＋+）
ﻩ{
ﻩﻩﻩＡ[i]＝nｅw inｔ [p[i]]［ｐ[i+１］］;
ﻩﻩﻩCreａtMaｔrｉx（A［i］，p［i]，ｐ［i+1]);
ﻩﻩ}
ﻩ｝
ﻩ//创建矩阵a，维数为ｍ*ｎ
ﻩpｒiｖａtｅ ｖoid ＣｒｅａtMａtrｉｘ（int [］［]a,int m，inｔ n)
ﻩ{
ﻩﻩfor(inｔ i＝０；i<m;i＋＋)
ﻩﻩﻩｆor（iｎt ｊ=０；j<n;j++)
ﻩﻩﻩ a[ｉ］［j］=（ｉnt） Ｍａｔh．ｒｏｕnｄ（Maｔh。raｎｄｏm(）＊９9)—5０;
｝
ﻩ／/输出连乘的所有矩阵
ｐrivａtｅ void pｒiｎｔＡｌｌＭ（）
ﻩ｛
ﻩ ｆor (int ｉ=０;ｉ〈thｉs．MＮ;i＋+)
ﻩﻩ｛
ﻩﻩ Ｓystｅｍ。out。prinｔｌｎ（＂Ａ”＋（i+1)＋"： "＋A[ｉ］．lengｔｈ +＂＊”＋Ａ[i］［０］．lenｇｔｈ )；
ﻩﻩﻩｐrｉｎtＭ（A[ｉ]);
ﻩﻩ｝
ﻩ｝
ﻩ//输出矩阵a的每个元素
ﻩｐrivate ｖoid prｉnｔＭ(iｎｔ ［］［］a）
ﻩ｛
ﻩﻩfｏr（iｎt i=0;ｉ〈a．ｌｅｎｇｔh ;i+＋）
ﻩ｛
ﻩﻩﻩSｙsteｍ。out。pｒiｎt（” "）；
ﻩﻩﻩfｏｒ（ｉnt j＝0；j〈a[i]。ｌｅnｇth；j++)
ﻩ ﻩﻩSｙｓｔｅm。out。pｒｉｎt(Sｔriｎg。ｆｏrmat(”％4ｄ”, a［i］［j]))；
ﻩﻩﻩSysｔem。ouｔ。ｐrｉｎtln（）；
ﻩ｝
ﻩ}
ﻩpｕblｉc ｓtａｔｉｃ voｉd main(Sｔrｉng ［] ａｒｇs)
ﻩ｛
ﻩﻩMaｔrｉx M=nｅw Ｍaｔｒix（７）；
ﻩﻩM。pｒintAlｌＭ（);
ﻩM。matｒiｘChaiｎ（M。ｐ，Ｍ。m,M。s）;
ﻩﻩSyｓtｅm．("矩阵链所需的最少乘次数为:”+[１］［M。MN］);
。prin