题目描述

有若干个矩阵{Ai}，元素都为整数且已知矩阵大小。
如果要计算所有矩阵的乘积A1 * A2 * A3 .. Am，最少要多少次整数乘法？

输入
第一行一个整数n(n <= 100)，表示一共有n-1个矩阵。
第二行n个整数B1, B2, B3… Bn(Bi <= 100)，第i个数Bi表示第i个矩阵的行数和第i-1个矩阵的列数。
等价地，可以认为第j个矩阵Aj(1 <= j <= n - 1)的行数为Bj，列数为Bj+1。
输出
一个整数，表示最少所需的乘法次数
样例输入
6
10 1 50 50 20 5
样例输出
3650

解题思路

矩阵A1（3行4列），矩阵A2（4行5列），A1*A2=A3（3行5列），A3中一共有十五个元素，计算每个元素都需要做4次乘法，因此计算矩阵A3一共要做3*4*5次乘法运算

下列四个矩阵M1(10*20)、M2（20*50）、M3（50*1）、M4（1*100）
M1(M2(M3M4)) 共需125000次乘法
(M1(M2M3))M4 共需2200次乘法
不同的相乘顺序，所需要的乘法次数是有差别的

现在假如要计算Ai*A2*A3*… Ak*…Aj的值，则肯定存在某个k值将这些矩阵分成两部分，使得Ai*A2*A3*…Ak*…Aj的值最小，分割成的两个子问题需要各自分别递归，寻找各自的最小值，然后再加上两个子问题相乘所需的乘法次数

递归解法：
假设计算m[i][j] 为计算Ai*A2*A3*… Ak*…Aj的乘法运算的最小值，同理Ai*A2*A3*…Ak的最小值为m[i][k]，矩阵Ai的维数为：p[i-1]p[i]
假如现在分割成的两部分已经各自找到自己的最小值，则Ai*A2*A3*… Ak*…Aj的最小值为：
m[i][j] = m[i][k] + m[k+1][j] +p[i-1] * p[k] * p[j]
如果i==j，则说明此时只有一个矩阵，无法继续分割，则m[i][j] = 0;
如果i < j，则m[i][j] = m[i][k] + m[k+1][j] +p[i-1] * p[k] * p[j]；

在递归计算过程中，可以引入备忘录，防止m[i][j]计算多次。

递归解法

package com.cn;

package com.cn;

import java.util.Scanner;

public class Matix3 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int []a = new int[n];

        for(int i=0; i<n ; i++){
            if(sc.hasNextInt()){
                a[i] = sc.nextInt();
            }
        }

        int [][]b = new int[n][n];
        int [][]c = new int[n][n];

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i == j)
                    b[i][j] = 0;
                else
                b[i][j] = Integer.MAX_VALUE;
            }
        }

        System.out.println(cut(a,b,c,1,a.length-1));
        output(c,1,a.length-1);

    }

    public static int cut(int[] a,int[][] b,int[][] c,int start,int end){

//      if(start == end){
//          b[start][end] = 0;
//          return 0;
//      }

        if(b[start][end] < Integer.MAX_VALUE){
            return b[start][end]; //如果有值，直接返回，相当于搜索
        }

        for(int i=start; i<end ; i++){
            int sum = cut(a,b,c,start,i) + cut(a,b,c,i+1,end) + a[start-1]*a[i]*a[end];//只计算一次，第二次查表得到

            if(sum < b[start][end]){
                b[start][end] = sum;
                c[start][end] = i;
            }
        }

        return b[start][end];
    }

    public static void output(int[][] c,int start,int end){
        if(start == end)
            System.out.print("A" + start);
        else{
            System.out.print("(");
            output(c,start,c[start][end]);
            output(c,c[start][end]+1,end);
            System.out.print(")");
        }
    }


}