• 设从矩阵Ai 到 Aj 的矩阵序列为 A[i:j] , m[][] 存放最小乘法次数 ,自底向上求解求解 , 即从子链长度为1 逐步求解子链长度为n的解

      • 当 i==j 时 , 不需要乘 , m[i][i] = 0

        • 自底向上求解问题的解 ,
          • 当子链长度为1的时候无需求解 , 及m[i][i] = 0

      • 当i != j时候, 需要根据子问题的解来计算当前解

        • m[i:j] = MIN{ m[i:k] +m[k+1] + ppp| k∈[i,j) }
          • 尝试当前子链A[i:j]的所有断点(遍历) , 获得当前问题的最优解
        • m[i:k] , 该子链长度小于m[i:j] 的长度 , 所以此时一定已经存在m[i:k]最优解
        • m[k+1:j] , 同上当前就是最优解
    1. /*
    2. 矩阵连乘问题-动态规划
    3. */
    4. #include<stdio.h>
    5. #include<stdlib.h>
    6. #include<time.h>
    7. //矩阵最大行/列 数
    8. const int MAXSIZE = 101;
    9. //矩阵最小的行/列 数
    10. const int MINSIZE = 2;
    11. //存放最优问题的断点
    12. int s[MAXSIZE][MAXSIZE];
    13. //存放子问题结果
    14. int m[MAXSIZE][MAXSIZE];
    15. //最多的矩阵的个数+1
    16. const int MNUM = 3;
    17. //存放可连乘矩阵的所有行列下标 , 由于 上一个矩阵的列等于下一个矩阵的行数
    18. //故第n个矩阵的    行数为p[n-1]    列数为p[n]
    19. int p[MNUM+1];
    21. int tt = 0;
    22. //输出问题解                   可以省略最高维度的大小
    23. void printres(int l, int r, int s[][MAXSIZE],int flag) {
    24.     if (l == r) {
    25.         printf("%d:%d", p[l - 1], p[l]);
    26.         return;
    27.     }
    28.     //printf("%d %d\n", l, r);
    29.     //system("pause");
    30.     if (flag) {
    31.         printf("(");
    32.         printres(l, s[l][r], s,0);
    33.         printf(")(");
    34.         printres(s[l][r] + 1, r, s,0);
    35.         printf(")");
    36.     }
    37.     else {
    38.         printf("[");
    39.         printres(l, s[l][r], s,1);
    40.         printf("][");
    41.         printres(s[l][r] + 1, r, s,1);
    42.         printf("]");
    43.     }
    44. }
    46. //动归解决问题
    47. void solve() {
    48.     //A[i][i] 的乘法次数为0
    49.     for (int i = 1; i <= MNUM; i++) {
    50.         m[i][i] = 0;
    51.     }
    52.     //矩阵连乘子链的长度从2增长
    53.     for (int r = 2; r <= MNUM; r++) {
    54.         //i为r长度子链的起始下标 
    55.         for (int i = 1; i <= MNUM - r + 1;i++) {
    56.             //j为r长度子链的尾下标
    57.             int j = i + r - 1;
    60.             //k ∈[i:j)
    61.             //先计算k = i 时的计算次数
    62.             m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
    63.             s[i][j] = i;
    64.             for (int k = i + 1; k < j; k++) {
    65.                 int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
    66.                 if (temp < m[i][j]) {
    67.                     s[i][j] = k;
    68.                     m[i][j] = temp;
    69.                 }
    70.             }
    72.         }
    74.     }
    76. }
    77. int main()
    78. {
    79.     while (1)
    80.     {
    81.         srand(time(NULL));
    82.         for (int i = 0; i <= MNUM; i++) {
    83.             //确定每个矩阵的行列数
    84.             p[i] = (rand() % (MAXSIZE - MINSIZE))+MINSIZE;
    85.             printf("%d ", p[i]);
    86.         }
    87.         printf("\n");
    89.         /*
    90.         p[0] = 10;
    91.         p[1] = 100;
    92.         p[2] = 5;
    93.         p[3] = 50;
    94.         for (int i = 0; i <= MNUM; i++) {
    95.             printf("%d ", p[i]);
    96.         }
    97.         printf("\n");
    99.         */
    102.         solve();
    103.         printres(1, MNUM, s,1);
    104.         printf("最小乘法次数为 : %d\n", m[1][MNUM]);
    105.         system("pause");
    106.     }
    107.     return 0;
    108. }
    111. /*
    112. p[0] - p[3] = 10 100 5 50
    113. */