文章目录一、问题说明二、解题思路一、状态定义二、状态转移方程定义三、初始化四、计算方式三、代码实现四、执行结果五、思考
一、主题说明
给出n个矩阵{A1、A2、A3、…、An}，其中Ai和ai1(I=1,2、2、…、n-1 )可乘。 用括号的方法表示矩阵的连乘顺序。 计算量(乘法次数)因计算顺序而异。 请找到加括号的方法，使矩阵连乘的计算量最小。
将2个矩阵Mixj、Mjxp的乘法次数设为i x j x p。
示例：
A1是M5x10的矩阵
A2是M5x100的矩阵
A3是M100x2的矩阵
有两种方法可以加括号：
(1) A1A2) A3；
(2) A1 ) A2A3 )；
第一种加括号方法的运算量：5 x 10 x100 5 x 100 x 2=6000；
第二种加括号方法的运算量： 10x 100 x2 5 x 10 x 2=2100；
二、解题思路输入矩阵如下表。
将矩阵A1A2A3A4A5大小3 x 55 x 1010 x 88 x 22 x 4转换为数组p，如下所示：
p[0] P[1] p [2] p [3] p [4] p [5] 3510824，因此p [0]和P[1]表示A1，p [1]和p [2]表示A2，依此类推。
1 .定义状态的dp[i][j]表示从Ai到bqdxf所需的最小计算量，I和j从1开始计数，最终求出的是dp[1][P.length -1]从矩阵A1到An的最小计算量。 其中，n=P.length -1；
或者，也可以分割dp[i][j]。 如果I和j满足j - i=1，则I和j之间一定有k。 也就是说，k表示矩阵Ak。 可以从Ak中划分出两个序列(Ai到Ak )和(Ak 1到bqdxf )，其中两个序列的乘法最少的计算量分别为dp[i][k]和dp[k 1][j]。 两个子序列矩阵加起来的计算量是P[i-1] x P[K] x P[j]。 因此，DP [ I ] [ j ]=DP [ I ] [ k ] DP [ k1 ] [ j ] p [ I-1 ] XP [ k ] XP [ j ]，当然位置k可能有多个，但收取最小费用。
2 .定义状态转移方程式j - i=0时，有
d p [ i ] [ j ]=0 dp[i][j]=0 dp[i][j]=0
不然的话
dp[I][j]=max(dp[I][k]dp[k][j]p
[ i − 1 ] × P [ k ] × P [ j ] ) , i ≤ k < j dp[i][j] = max( dp[i][k] + dp[k][j] + P[i-1] times P[k] times P[j]), i leq k < j dp[i][j]=max(dp[i][k]+dp[k][j]+P[i−1]×P[k]×P[j]),i≤k<j 3. 初始化 当j - i <= 0时，有 d p [ i ] [ j ] = 0 dp[i][j] = 0 dp[i][j]=0
4. 计算方式 自底向上，自左向右计算。这里解释下是指dp二维表自底向上是指i从大往小计算，自左向右计算是指j从小到大计算。
三、代码实现 /** * 最小矩阵乘法运算数量 * * @author hh * @date 2021-5-18 23:32 */public class MinMatrixChain { public int minCalcCount(int[] matrix, int[][] trace) { if (matrix.length < 3) { throw new IllegalArgumentException("非法参数"); } int[][] dp = new int[matrix.length][matrix.length]; for (int i = matrix.length - 1; i >= 1; i--) { for (int j = 1; j <= matrix.length-1; j++) { if (j - i == 0) { dp[i][j] = 0; continue; } dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int temp = dp[i][k] + dp[k+1][j] + matrix[i - 1] * matrix[k] * matrix[j]; if (temp < dp[i][j]) { dp[i][j] = temp; trace[i][j] = k; } } } } return dp[1][matrix.length-1]; } public void print(int[] matrix, int[][] trace, int startIndex, int endIndex) { if (endIndex - startIndex <= 0) { System.out.print("A" + startIndex + " "); } else { System.out.print("("); print(matrix, trace, startIndex, trace[startIndex][endIndex]); print(matrix, trace, trace[startIndex][endIndex] + 1, endIndex); System.out.print(")"); } } public static void main(String[] args) { int[] matrix = new int[]{3, 5, 10, 8, 2, 4}; int[][] trace = new int[matrix.length][matrix.length]; MinMatrixChain minMatrixChain = new MinMatrixChain(); System.out.println(minMatrixChain.minCalcCount(matrix, trace)); minMatrixChain.print(matrix, trace, 1, matrix.length-1); }} 四、执行结果 五、思考 本题和字符串切分的做法非常相似，都是对dp数组进行线性划分，读者有时间可以看我的另一篇文章动态规划经典题目-字符串切分，进行举一反三。