《动态规划——矩阵连乘》由会员分享，可在线阅读，更多相关《动态规划——矩阵连乘（3页珍藏版）》请在金锄头文库上搜索。
代码：#includeusing namespace std;const int MAX = 100;/p 用来记录矩阵的行列，main 函数中有说明/mij用来记录第 i 个矩阵至第 j 个矩阵的最优解/s用来记录从哪里断开的才可得到该最优解int pMAX+1,mMAXMAX,sMAXMAX;int n;/矩阵个数void matrixChain()for(int i=1;in;for(int i=0;ipi;/测试数据可以设为六个矩阵分别为/A130*35,A235*15,A315*5,A45*10,A510*20,A620*25/则 p0-6=30,35,15,5,10,20,25/输入：6 30 35 15 5 10 20 25matrixChain();traceback(1,n);/最终解值为 m1n;coutj，则 mij=minmik+mk+1j+pi-1XpkXpj,其中 k,在 i 与 j之间游荡，所以 i=kj ;代码实现时需要注意的问题：计算顺序！因为你要保证在计算 mij查找 mik和 mk+1j的时候，mik和 mk+1j已经计算出来了。观察坐标的关系如图：所以计算顺序如上右图：相应的计算顺序对应代码为 13-15 行m1n即为最终求解，最终的输出想为（A1（A2 A3）（A4 A5）A6）的形式，不过没有成功，待思考.
