动态规划解决矩阵连乘问题

3.7 矩阵连乘(Matrix chain multiplication)

3.7.1 问题描述

求多个矩阵连乘的最优次序，使得所需的乘法次数最少，并求出所需的乘法次数。

3.7.2 算法思路

跟以往的动态规划解题思路相同，要求A1~A5的连乘，就先求A1A2的，再求A1A2A3的…
我们需要填写下列这张表，它记录了每个子问题的值

按照上图的填写思路，我们最终填完所有的表，即下图的左表。
而下图的右侧表格代表的是括号的位置，比如我们在填（A1,A3）这格时，发现橙色的，也就是A1(A2A3)的乘法次数最少，所以我们把这个方案填入了下图的左表，此时括号是在A2前面，因此在右表填入2。

左表的(A1，A5)格就是我们要求的最少乘法次数，而根据右表，我们可以看出对应的连乘顺序。
最终我们得出，最少乘法次数为174，顺序为：(A1(A2A3))(A4A5)
注意：不要死记硬背填表方式，应该理解表格填法所代表的矩阵连乘的含义。

3.7.3 代码实现

public static int getMinMultiplicationNum(int[] dims) {//若有n个矩阵，则数组维数设置为n+1
	int n = dims.length-1;
	int[][] tab_num = new int[n][n];//建表，存乘法次数
	int[][] tab_split = new int[n][n];//建表，存括号位置
	/*核心*/
	for(int j=1;j<n;j++){//列，一列一列走，且从下往上
		for(int i=j-1;i>=0;i--){//行
			tab_num[i][j] = tab_num[i][j-1] + dims[i]*dims[j]*dims[j+1];//赋初值
			tab_split[i][j] = j;
			for(int k=i+1;k<j;k++){
				if(tab_num[k][j] + tab_num[i][k-1] + dims[i]*dims[k]*dims[j+1] < tab_num[i][j]){
					tab_num[i][j] = tab_num[k][j] + tab_num[i][k-1] + dims[i]*dims[k]*dims[j+1];
					tab_split[i][j] = k;
				}
			}
		}
	}
	trackback(tab_split,0,n-1);
	System.out.println();
	return tab_num[0][n-1];
}
//
//输出连乘顺序
private static void trackback(int[][] tab_split, int i, int j) {
	if(i == j) {
		System.out.print("A" + (i+1));
	}
	else{
		System.out.print("(");
		trackback(tab_split,i,tab_split[i][j]-1);
		trackback(tab_split,tab_split[i][j],j);
		System.out.print(")");
	}
}