矩阵相乘题目查看动态规划优点

这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战

题目

输入一个数组**P**如P={30,35,15,5,10,20}，大小为n=5，相应的矩阵为：A1<30,35> ,A2<35,15> ,A3<15,5> ,A4<5,10> ,A5<10,20>

计算A1到A5矩阵相乘的最优解

方法一共有两种：

第一种：分治算法

使用分治算法的步骤为

	1. 求出最小子问题解 
	2. 分解问题
	3. 找递归方程式
	4. 合并问题
复制代码

套用到本题中，题目要求为计算A1到A5矩阵相乘的最优解 **最小子问题：**m[i,i] = 0 分解问题： 分割为两个矩阵相乘

递归方程式 ：当 l = r 时 sum = 0

​ 当l < r 时 sum = sum(l,l+1)

合并问题： min[i] = sum(p,l,l + i)+sum(p,l+i+1,r)+p[l-1] * p[i+l] * p[r];

代码如下：

public class Matriz {
    public static void main(String[] args) throws ParseException {
        long time = System.nanoTime();
        int n = 100;
        int [][]num = new int[n][n];
        int p[] = {30,35,15,5,10,20,30,35,15,5,10,20,30,35,15,5,10,20,30,35,15,5,10,20,30,35,15,5,10,20};
        int sum = sum(p, 1, 6);
        Date endDate = new Date();
        long endTime = System.nanoTime();
        System.out.println(sum);
        System.out.println(endTime -time + "ns");
    }

    private static int sum(int[] p, int l, int r) {
        if (l == r) return 0;
        int min[] = new int[100];
        for (int i = 0; l+i < r ; i++) {
            min[i] = sum(p,l,l + i)+sum(p,l+i+1,r)+p[l-1]*p[i+l]*p[r];
        }
        int min_ = min[0];
        for (int i = 0; l+i < r; i++) {
            if (min_ > min[i]){
                min_ = min[i];
            }
        }
        return min_;
    }
}
复制代码

第二种：动态规划

为什么要使用动态规划呢？

从第一种方法可以看出，分治算法虽然使用方便，也比较好理解，和想出。但是它也有一个缺点，会进行重复运算。比如A1和A2两个矩阵相乘，在A1到A5矩阵相乘的递归中会重复计算4次，那如果是A1到A100呢就会重复计算99次，如果数字在大一点，重复计算的次数就会越来越大。为了避免这个问题我们可以使用动态规划。动态规划的优点就是会在计算一次最优解后，会记录下来，已供后面使用，这样就避免了重复运算。

在这个问题里我们只要解决两问题就可以了

1. 填表：填表我们采用斜向遍历上三角来填表
2. 计算最小值：则使用公式 min[i] = num[ k ][ k + i ]+num[k+i+1][j]+p[k]* p[i+k+1] *p[j+1]；来分别计算矩阵相乘的结果，最后比较求出最小值

import java.util.Scanner;

/**
 * 矩阵相乘
 * 
 */
public class Test01 {

    public static int min(int [] p,int k,int j,int num[][]){
        int min[] = new int[100];
        for (int i = 0; k+i < j ; i++) {
           min[i] = num[k][k+i]+num[k+i+1][j]+p[k]*p[i+k+1]*p[j+1];
        }
        int sum = min[0];
        for (int i = 0; k+i < j; i++) {
            if (sum > min[i]){
                sum = min[i];
            }
        }
        return sum;
    }
    public static void main(String[] args) {

//        System.out.println("请输入矩阵大小：");
//        Scanner scanner = new Scanner(System.in);
        int n = 6;
        int [][]num = new int[n][n];
        // 49 54
        int p[] = {30,35,15,5,10,20,20};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < (n-i); j++) {
                if (j == j+i){
                    num[j][j+i] = 0;
                }else {
                    num[j][j+i] = min(p,j,j+i,num);
                }
                System.out.print(num[j][j+i]+"   ");
            }
            System.out.println("");
        }

    }
}
复制代码