动态规划解决矩阵连乘问题

package workfive; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.Scanner; //原问题的最优解包含子问题的最优解 public class Main { static int N=100; static int []p=new int[N];//记录矩阵的行和列，第i个矩阵的行数存储在数组的第i-1个位置，列数存储在数组的第i个位置。 static int [][]m=new int[N][N];//表示AiAi+1A...Aj矩阵连乘的最优值（最小值） static int [][]s=new int[N][N];//存放各个子问题的最优决策,记录M[i][j]最小时断开点K的位置 static int n;//多少个数组 static void matrixchain(){ int i,j,r,k; //初始化数组，使m[][],s[][]对角线上的元素为0 for( i=0;i<N;i++){ for (j=0;j<N;j++){ if(i==j){ m[i][j]=0; s[i][j]=0; } } } for(r=2;r<=n;r++){//r为问题规模，处理不同规模的子问题 for(i=1;i<=n-r+1;i++){ j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//决策为k=i的乘法次数 s[i][j]=i;//子问题的最优策略是i for(k=i+1;k<j;k++){//对从i+1到j的所有决策，求最优值 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t<m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } } static void print(int i,int j){ if(i==j){ System.out.print("A["+i+"]"); return; } System.out.print("("); print(i,s[i][j]); print(s[i][j]+1,j); System.out.print(")"); } //写入文件 public void Write() throws IOException{ int num; int[] a=new int[n+1]; //循环生成随机数，存到数组a中 for(int i=0;i<a.length;i++){ num=(int) (Math.random()*10+1); a[i]=num; } File file=new File("D:\\input.txt"); FileWriter out = new FileWriter(file); //循环将数组写入文件 for(int i=0;i<a.length;i++){ out.write(a[i]+"\t"); } out.close(); } //读取文件内容 public int[] Read() throws IOException{ int[] b=new int[n+1]; File file=new File("D:\\input.txt"); BufferedReader in=new BufferedReader(new FileReader(file)); String line=in.readLine(); String[] temp=line.split("\t"); //循环将文件中值赋给数组 for(int j=0;j<temp.length;j++){ b[j]=Integer.parseInt(temp[j]); } in.close(); return b; } public static void main(String[] args) throws IOException { Scanner sc=new Scanner(System.in); System.out.println("请输入矩阵的个数n个数："); n=sc.nextInt(); Main a =new Main(); a.Write(); int o[]=new int[n+1]; o=a.Read(); for(int i=0;i<n+1;i++){ p[i]=o[i]; } // Scanner sc=new Scanner(System.in); // System.out.println("请输入矩阵的个数n个数："); // n=sc.nextInt(); // int i,j; // System.out.println("请一次输入每个矩阵的行数和最后一个矩阵的列数："); // for (i=0;i<=n;i++){ // p[i]=sc.nextInt(); // } matrixchain(); print(1,n); System.out.println(); System.out.println("最小计算量的值为："+m[1][n]); } }