动态规划——矩阵连乘有关问题

动态规划——矩阵连乘问题

两个矩阵相乘的计算量

程序实现

1、（A（BCD））——>（A（B（CD））），（A（（BC）D））;2、（（AB）（CD））——>NULL；3、（（ABC）D）——>（（A（BC）D）），（（（AB）C）D）;对于上面四个矩阵来说，枚举方法是：1、括号加在A和B之间，矩阵链被分为（A）和（BCD）；2、括号加在B和C之间，矩阵链被分为（AB）和（CD）；3、括号加在C和D之间，矩阵链被分为（ABC）和（D）；在第一步中分出的（A）已经不能在加括号了，所以结束；而（BCD）继续按照上面的步奏把括号依次加在B和C、C和D之间，其他情况相同。加括号的过程是递归的。
程序实现

上图为递归枚举过程，小方块内的1:4代表第1个矩阵至第4个矩阵的完全加括号方式
可以看到黄色方块中有很多重复计算，所以利用备忘录来保存计算结果，在每次进行计算前，先查表，看是否计算过，避免重复计算。
程序实现


k为矩阵链断开的位置d数组存放矩阵链计算的最优值，d[i][j]是以第i个矩阵为首，第j个矩阵为尾的矩阵链的最优值，i > 0m数组内存放矩阵链的行列信息，m[i-1]和m[i]分别为第i个矩阵的行和列（i = 1、2、3...）
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define SIZE 100#define INF 999999999int m[SIZE];//存放矩阵链的行列信息，m[i-1]和m[i]分别为第i个矩阵的行和列（i = 1、2、3...）int d[SIZE][SIZE];//存放矩阵链计算的最优值，d[i][j]为第i个矩阵到第j个矩阵的矩阵链的最优值，i > 0int Best_DP(int n){//把d[i][i]置为0，1 <= i < nmemset(d, 0, sizeof(d));int len;//递归计算矩阵链的连乘最优值//len = 1，代表矩阵链由两个矩阵构成for (len = 1; len < n; len++){int i, j, k;for (i = 1, j = i+len; j < n; i++, j++){int min = INF; //无穷大for (k = i; k < j; k++){int count = d[i][k] + d[k+1][j] + m[i-1] * m[k] * m[j];if (count < min){min = count;}}d[i][j] = min;}}return d[1][n-1];}int main(void){int n;while (scanf("%d", &n) != EOF){int i;for (i = 0; i < n; i++){scanf("%d", &m[i]);}printf("%d\n", Best_DP(n));}return 0;}