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();}}
}