maxtrain.java

算法导论上机作业java实现

public class  Maxtrain {
      public static int[][] MaxTrain(int[] p){
    	  int n = p.length-1;
    	  int[][] m = new int [n][n];
    	  int[][] 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 =1;i<n-l+1;++i)
    		  {
    			  int j = i+l-1;
    			  m[i][j] = Integer.MAX_VALUE;
    			  for(int k = i;k<=j-1;++k)
    			  {
    				  int 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;
    				  }
    			  }
    		  }
    	  }
    	  return s;
      }
      public static void Print(int[][] s,int i,int j){
    	  //int[] p = new int p[7];
    	  if(i==j)
    		  System.out.print("A["+(i+1)+"]");
    	  else
    	  {
    		  System.out.print("(");
    		  Print(s,i,s[i][j]);
    		  Print(s,s[i][j]+1,j);
    		  System.out.print(")");
    	  }
      }
      
	public static void main(String[] args) {
		int[] p ={5,10,3,12,5,50,6};
		Print(MaxTrain(p),0,p.length -2);

	}

}