区间dp 矩阵连乘

题目解析:

这里最后一句话第i个矩阵是a[i]*a[i-1]好像不太好理解,但其实就是说这是一个a[i-1]行a[i]列的一个矩阵

所以说两个矩阵相乘比如矩阵1乘以矩阵2,矩阵1是a[0]行a[1]列,矩阵二是a[1]行a[2]列,正好矩阵1矩阵2满足矩阵乘法原则,运算量也就是a[0]*a[1]*a[2]

(矩阵乘法没啥好说的)到这里题意差不多清楚了

然后我们很轻易就可以看出来这是一个区间动归,也就是将有不同的组合,让我们去找最优解(跟石子合并题面好相似)

我们用dp[i][j]表示从i到j的最小运算量,可以看出只有两个矩阵相乘时才会出现所谓的“运算量”,故i=j时,运算量为0.

我们用k表示断点,那么dp[i][k]形成a[i-1]行a[k]列矩阵要和dp[k+1][j]形成a[k]行a[j]列矩阵再相乘

就得到了动态转移方程dp[i][j]=min(dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);

代码:

原文地址:https://www.cnblogs.com/TheSure/p/12849701.html