GDPU 算法分析与设计天码行空5

一、【实验目的】

（1）熟悉动态规划算法的基本思想.
（2）理解动态规划算法中子问题的划分和递推方程设计的基本方法.
（3）熟悉矩阵链乘法的基本思想并编程实现。

二、【实验内容】

输入:矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>，其中:1<=i<=j<=n.

输出:计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。

三、实验源代码

💖 Main.java

import java.util.Scanner;

public class Main {
    private static final int N = 101;
    private static int[][] m = new int[N][N];
    private static int[][] s = new int[N][N];
    private static int[] a = {30, 35, 15, 5, 10, 20};

    public static int recursiveMatrixChain(int[] a, int i, int j) {
        if (i == j) {
            m[i][j] = 0;
            s[i][j] = i;
            return m[i][j];
        }
        m[i][j] = Integer.MAX_VALUE;
        s[i][j] = i;
        for (int k = i; k < j; k++) {
            int q = recursiveMatrixChain(a, i, k) + recursiveMatrixChain(a, k + 1, j) + a[i - 1] * a[k] * a[j];
            if (q < m[i][j]) {
                m[i][j] = q;
                s[i][j] = k;
            }
        }
        return m[i][j];
    }

    public static void main(String[] args) {
        recursiveMatrixChain(a, 1, 5);
        System.out.println("The number of least multiplication operations:");
        System.out.println(m[1][5]);
        System.out.println("Position of the last operation:");
        System.out.println(s[1][5]);
        System.out.println("Array s:");
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                System.out.print(s[i][j] + " ");
            }
            System.out.println();
        }
    }
}