【动态规划】 n个矩阵连乘问题

• 递归算法

package com.example.demo;

public class Test5 {

	static int[] r = {0, 5, 20, 50, 1, 100}; //r1,r2,r3,r4,r5
	static int[][] dp = new int[30][30]; // dp[i][j] --> 矩阵 Mi * Mi+1 * Mi+2 ...  * Mj (i<j)
	static int[][] com = new int[30][30]; // dp[i][j] --> 矩阵 Mi ~ Mj 相乘的组合点 k.  即： Mij = Mi * ... Mk + Mk+1 * ... Mj
	static int n = 4;//

	public static void main(String[] args) {

		System.out.println(minValue(1, 4));
		for (int i = 1; i <= n; i++) {
			System.out.println();
			for (int j = 1; j <= n; j++)
				System.out.printf(com[i][j] + " ");
		}
		System.out.println();
		combine(1, 4);

	}

	static int minValue(int i, int j) {
		if (i == j) {
			dp[i][j] = 0;
			return 0;
		}
		if (dp[i][j] != 0) {
			return dp[i][j];
		}
		if (j == i + 1) {
			com[i][j] = i;
			dp[i][i + 1] = r[i] * r[i + 1] * r[i + 2];
			return r[i] * r[i + 1] * r[i + 2];
		}
		// i< j
		int min = Integer.MAX_VALUE;
		for (int k = i; k < j; k++) {
			int currentValue = minValue(i, k) + minValue(k + 1, j) + r[i] * r[k + 1] * r[j + 1];
			if (min > currentValue) {
				min = currentValue;
				com[i][j] = k;
			}
		}
		dp[i][j] = min;
		return min;
	}

	//输出算法
	static void combine(int i, int j) {
		if (i == j)
			return;
		combine(i, com[i][j]);
		combine(com[i][j] + 1, j);
		System.out.printf("M[" + i + com[i][j] + "]");
		System.out.printf(" and  M[" + (com[i][j] + 1) + "" + j + "]");
		System.out.println();
	}
}

• 输出：

• 非递归算法

  package com.example.demo;
  
  public class Test5 {
  
  	static int[] r = {0, 5, 20, 50, 1, 100}; //r1,r2,r3,r4,r5
  	static int[][] m = new int[30][30]; //
  	static int[][] com = new int[30][30]; //
  	static int n = 4;//
  
  	public static void main(String[] args) {
  		for (int i = 1; i < n; i++) {
  			m[i][i] = 0;
  			com[i][i + 1] = i;
  			m[i][i + 1] = r[i] * r[i + 1] * r[i + 2];
  		}
  		for (int s = 2; s < n; s++) {
  			for (int i = 1; i < n - s + 1; i++) {
  				int j = i + s;
  				// i: 起始位置  j:终点位置
  				m[i][j] = m[i][i] + m[i + 1][j] + r[i] * r[i + 1] * r[j + 1];
  				com[i][i] = i;
  				for (int k = i + 1; k < j; k++) {
  					int t = m[i][k] + m[k + 1][j] + r[i] * r[k + 1] * r[j + 1];
  					if (t < m[i][j]) {
  						m[i][j] = t;
  						com[i][j] = k;
  					}
  				}
  			}
  		}
  		System.out.println(m[1][n]);
  
  		for (int i = 1; i <= 4; i++) {
  			for (int j = 1; j <= 4; j++) {
  				System.out.printf(com[i][j] + " ");
  			}
  			System.out.println();
  		}
  	}
  
  }

参考文章