simplematrixchain.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//19 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.matrixchain;

public class SimpleMatrixChain extends AbstractMatrixChain {

	public long matrixChainOrder() {
		int n = p.length -1;
		long[][] m = new long[n][n];
		s = new int[n][n];
		for(int i=0;i<n;i++){
			m[i][i] = 0;
		}
		for(int l=2;l<=n;l++)
			for(int i=0;i<n-l+1;i++){
				int j=i+l-1;
				m[i][j] = Long.MAX_VALUE;
				for(int k=i;k<j;k++){
					long q = m[i][k]+m[k+1][j] +p[i]*p[k+1]*p[j+1];
					if(q<m[i][j]){
						m[i][j] = q;
						s[i][j] = k;
					}
				}
			} 
		ans = m[0][n-1];
		return ans;
	}

}