利用动态规划计算以下矩阵连乘：A1(20*25)、A2(25

import java.util.Scanner;
public class MainTest{
    public static void main(String[] args){
        int n;//一共有多少个矩阵
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        //存放矩阵的行数和列数
        int[] p= new int[n+1];//矩阵A1的行数和列数是p0,p1，以此类推
        Scanner in = new Scanner(System.in);
        for(int i = 0;i<p.length;i++){
            p[i] = in.nextInt();
        }
        //然后开始填表
        int[][] m = new int[n+1][n+1];//m[i][j]表示i矩阵到j矩阵最少的乘法次数
        int[][] s = new int[n+1][n+1];//s[i][j]表示i矩阵到j矩阵从哪个地方画括号
        for(int i = 1; i <= n; i++){
            for(int j = 1;j<=n;j++){
                if(i == j){
                    m[i][j]=0;//比如说m[1][1],矩阵1到矩阵1，一个矩阵没法乘，所以乘法次数为0
                }
            }
        }
        for(int r = 2;r<=n;r++){
            for(int k = 1;k <= n-r+1;k++){
                int g =  k+r-1;
                m[k][g] = m[k+1][g] + p[k-1]*p[k]*p[g];//纵向
                //算每个对角线。m[1][2] = m[2][2]+p0*p1*p2;隐藏了m[1][1]
                //m[1][3] = m[2][3] + p0*p2*p3;//隐藏了m[1][1];
                //m[2][4] = m[3][4] + p2*p3*p4隐藏了m[2][2];
                s[k][g] = k;//分割位置
                for(int b = k+1;b<g;b++){//横向
                    int t = m[k][b]+m[b+1][g]+p[k-1]*p[b]*p[g];
                    if(t < m[k][g]){
                        m[k][g] = t;
                        s[k][g] = b;
                    }
                }
            }
        }
        //System.out.println(m[1][n]);
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                System.out.print(s[i][j]+" ");
            }
            System.out.println();
        }
    }
}