本文共 2943 字，大约阅读时间需要 9 分钟。

问题描述（动态规划）　　有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。　　两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。输入格式　　输入的第一行包含一个整数n，表示矩阵的个数。　　第二行包含n+1个数，表示给定的矩阵。输出格式　　输出一个整数，表示最少的运算次数。样例输入31 10 5 20样例输出150数据规模和约定　　1<=n<=1000, 1<=ai<=10000。

import java.util.Scanner;public class JuZheng {
           public void printResult(int[] arrayMatrix) {
           int length = arrayMatrix.length;  //有length个数，可知有length - 1个矩阵        long[][] dp = new long[length][length];  //dp[0][i]和dp[i][0]均为0，无意义        long sum;        for(int len = 2;len < length;len++) {
    //依次计算len个矩阵相乘的最小结果，即dp[1][len]            for(int i = 1, j = len;j < length;i++, j++) {
     //此层循环用于计算dp[i][j]值，即矩阵中对角线的元素值                long min = Long.MAX_VALUE;                for(int k = i;k < j;k++) {
    //此层循环，用于找到dp[i][j]的最小值                    sum = dp[i][k] + dp[k + 1][j] + arrayMatrix[i - 1] * arrayMatrix[k] * arrayMatrix[j];                    if(min > sum)                        min = sum;                }                dp[i][j] = min;            }        }        //输出最终结果        System.out.println(dp[1][length - 1]);        return;    }        public static void main(String[] args) {
           JuZheng test = new JuZheng();        Scanner in = new Scanner(System.in);        int n = in.nextInt();        if(n <= 1 || n > 1000)            return;        int[] arrayMatrix = new int[n + 1];        for(int i = 0;i <= n;i++)            arrayMatrix[i] = in.nextInt();        test.printResult(arrayMatrix);    }}

样例输入矩阵相乘2 3 2 1 0 -1 1 1 -3 0 3 1 2 3 1样例输出-3 2 -8 2

import java.util.Scanner;public class Juzhen {
       public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);        int m = 0 , s = 0 , n = 0 ;        if(scanner.hasNext()){
     //输入m,s,n            m = scanner.nextInt() ;            s = scanner.nextInt() ;            n = scanner.nextInt() ;        }        //定义两个矩阵,行列数分别为m,s与s,n        int arr1[][] = new int[m][s] ;        int arr2[][] = new int[s][n] ;        for(int i = 0 ; i < m ; i ++){
     //输入第一个矩阵            for(int j = 0 ; j < s ; j++){
                   if(scanner.hasNext()){
                       arr1[i][j] = scanner.nextInt() ;                }            }        }        for(int i = 0 ; i < s ; i++){
      //输入第二个矩阵            for(int j = 0 ; j < n ; j++){
                   if(scanner.hasNext()){
                       arr2[i][j] = scanner.nextInt() ;                }            }        }        int arr[][] = new int[m][n] ;   //定义一个相乘后的矩阵，矩阵的行数与列数为m，n        for(int i = 0 ; i < m ; i++){
      //进行矩阵相乘            for(int j = 0 ; j < n ; j++){
                   for(int x = 0 ; x < s ; x ++){
     //arr[i][j] = arr1[i][1] * arr2[1][j] + ... + arr1[i][s-1] * arr2[s-1][j]                     arr[i][j] += arr1[i][x] * arr2[x][j] ;                }                System.out.print(arr[i][j] + " ");            }            System.out.println();        }    }}

转载地址：http://cgrwi.baihongyu.com/