学校考试版-矩阵连乘

问题：给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1，求矩阵相乘至少需要多少次数乘？

举例：A1 10100，A2 1005，A3 550，则A1A2*A3至少需要7500次数乘。

算法设计

采用自底向上的方法求最优解，对于每一个小规模的子问题都求最优解，并记录最优策略（加括号的位置），具体算法设计如下。
（1）确定合适的数据结构
采用一维数组p[]来记录矩阵的行和列，第i个矩阵的行数存储在数组的第i-1位置，列数存储在数组的第i位置。二维数组m[][]来存放各个子问题的最优值，
（2）初始化
采用一维数组p[]来记录矩阵的行和列，m[i][j]=0,其中i=1,2,3,…,n。
（3）循环阶段
按照递归关系式计算2个矩阵A_i，A_i+1相乘的最优解，j=i+1,并将其存入m[i][j]。
按照递归关系式计算3个矩阵相乘A_i,A_i+1,A_i+2相乘时的最优值，j=i+2,并将其存入m[i][j]。
以此类推，直到求出n个矩阵相乘的最优值m[1][n]。

代码

import java.util.Scanner;
public class text5 {
    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];//存放各个子问题的最优决策
    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;
                    }
                }
            }
        }
    }
 public static void main(String[] args) {
        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();
        System.out.println("最小计算量的值为："+m[1][n]);
    }
}

输入

3
10  100  5  50

输出

7500    

运行示例