动态-矩阵连乘

最新推荐文章于 2021-05-02 00:00:51 发布

x_zhaohu

最新推荐文章于 2021-05-02 00:00:51 发布

阅读量317

点赞数 1

分类专栏：算法题

本文链接：https://blog.csdn.net/x_zhaohu/article/details/53858681

版权

算法题专栏收录该内容

44 篇文章

订阅专栏

public class MatrixFormDynamicProgramming {

	public static void matrixChain(int[] arrays, int[][] multiplicationTimes, int[][] result) {
		for(int i = 1; i < arrays.length; i++) {
			multiplicationTimes[i][i] = 0;
		}
		for (int r = 2; r < arrays.length; r++) {
			for(int i = 1; i <= arrays.length - r; i++) {
				int j = i+r-1;
				multiplicationTimes[i][j] = multiplicationTimes[i+1][j] + arrays[i-1]*arrays[i]*arrays[j];
				result[i][j] = i;
				for (int k = i + 1; k < j; k++) {
					int t = multiplicationTimes[i][k] + multiplicationTimes[k+1][j] + arrays[i-1]*arrays[k]*arrays[j];
					if (t < multiplicationTimes[i][j]) {
						multiplicationTimes[i][j] = t;
						result[i][j] = k;
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		int[] arrays = {30, 35, 15, 5, 10, 20, 25};
		int[][] multiplicationTimes = new int[arrays.length][];
		int[][] result = new int[arrays.length][];

		for (int i = 0; i < arrays.length; i++) {
			multiplicationTimes[i] = new int[arrays.length];
			result[i] = new int[arrays.length];
		}
		matrixChain(arrays, multiplicationTimes, result);
		System.out.println(multiplicationTimes[1][6]);
	}
}