3.1.2矩阵连乘问题(备忘录方法)

《3.1.2矩阵连乘问题(备忘录方法)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、备忘录是动态规划算法的变形.备忘录方法也是用表格保存已解决子问题的答案.与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的.因此,备忘录方法的控制结构与直接递归方法的控制结构相同,而区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解.备忘录方法为每个子问题建立一个记录项,并初始化为一个特殊值表示该子问题尚未求解.在求解过程中,对每个待求的子问题,首先查看其相应的记录项.如若记录项仍为初始化时的特殊值,则表示该子问题尚未

2、求解,于是对其求解;如若记录项非特殊值,则表示该子问题已求解,直接取值即可.#include#include#defineN100usingnamespacestd;intm[N+1][N+1]={0},s[N+1][N+1]={0},p[N+2]={0};//数组m用于记录子问题的解,数组s用于记录最佳分割点,数组p用于记录矩阵行列数.intLookUpdMatrixChain(inti,intj){if(m[i][j])returnm[i][j];if(i=

3、=j)return0;m[i][j]=LookUpdMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

4、最优方案.//A1~An的最佳分割点为s[1][n],//A1~As[1][n]的最佳分割点为s[1][s[1][n]];//而As[1][n]+1~An的最佳分割点为s[s[1][n]+1][n].//(跟前一种情况一摸一样,只是下标变了一下.)//依此类推...if(i==j)return;Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout<<"MultiplyA"<

5、)<<","<>n;for(inti=0;i<=n;++i)cin>>p[i];cout<

6、2,2MultiplyA1,2andA3,3