memorizedmatrixchain.java

《算法设计与分析》王晓东编著

public class MemorizedMatrixChain {

	public static int p[];  /* 矩阵链 */
	public static int s[][];  /* 记录断点的矩阵 */	
	public static int m[][];  /* 记录最优结果矩阵 */	
	
	public static int memorizedMatrixChain(int n)
	{
		for (int i=1;i<=n;i++)
		  for (int j=i;j<=n;j++)
			  m[i][j]=0;
		return lookupChain(1,n);		
	}
	
	private static int lookupChain(int i,int j)
	{
		if (m[i][j]>0) return m[i][j];
		if (i==j) return 0;
		int u=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];
		s[i][j]=i;
		for (int k=i+1;k<j;k++) {
			int t=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];
			if (t<u) {
				u=t;
				s[i][j]=k;
			}			
		}
		m[i][j]=u;
		return u;		
	}
	
	public static void main(String[] args) {
		/* 初始化矩阵链 A1(30*35), A2(35*15), A3(15*5), A4(5*10) */
		p=new int[]{30,35,15,5,10};
		int n=p.length;
		
		/* 初始化断点矩阵 */
		s=new int[n][n];
		
		/* 初始化最优结果矩阵 */
		m=new int[n][n];
		
		/* 求最优矩阵相乘计算次数 */
		System.out.println("min="+memorizedMatrixChain(n-1)+"\n");
	}
}