矩阵连乘的DP，两种方法(自下至上、自顶至下)

andalousie

基本上百度一下都可以搜到矩阵连乘的算法。大家写的都差不多是同一个思路(bottom-up DP，自下而上的动态规划)。这里再提供一个速度相仿的自上而下(top-down)的解法。代码属于C++。

1. // See the Cormen book for details of the following algorithm
   
2. #include<iostream>
   
3. #include<cstdio>
   
4. #include<climits>
   
5. 
   
6. class MatrixChain
   
7. {
   
8.         int     n;
   
9.         int ** m;
   
10.         int ** s;
    
11. public:
    
12.         MatrixChain(int size)
    
13.                 :n(size)
    
14.         {
    
15.                 /* For simplicity of the program, one extra row and one extra column are
    
16.        allocated in m[][].  0th row and 0th column of m[][] are not used */
    
17.                 m = new int* [n+1];
    
18.                 s = new int* [n+1];
    
19.                 for (int t = 0; t <= n; ++t)
    
20.                 {
    
21.                         m[t] = new int[n+1];
    
22.                         s[t] = new int[n+1];
    
23.                 }
    
24.         }
    
25.         ~MatrixChain()
    
26.         {
    
27.                 for (int t = 0; t <= n; ++t)
    
28.                 {
    
29.                         delete [] m[t];
    
30.                         delete [] s[t];
    
31.                 }
    
32.                 delete [] s;
    
33.                 delete [] m;
    
34.         }
    
35.         int MatrixChainOrder(int p[]);
    
36.         int MatrixChainOrderTD(int p[]);
    
37.         void traceback(int i, int j);
    
38.         int topdown(int p[], int i, int j);
    
39. };
    
40. 
    
41. // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
    
42. int MatrixChain::MatrixChainOrder(int p[])
    
43. {
    
44.     int i, j, k, L, q;
    
45. 
    
46.     /* m[i,j] = Minimum number of scalar multiplications needed to compute
    
47.        the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
    
48.        p[i-1] x p[i] */
    
49. 
    
50.     // cost is zero when multiplying one matrix.
    
51.     for (i = 1; i <= n; i++)
    
52.         m[i][i] = 0;
    
53. 
    
54.     // L is chain length.  
    
55.     for (L=2; L<=n; L++)   
    
56.     {
    
57.         for (i=1; i<=n-L+1; i++)
    
58.         {
    
59.             j = i+L-1;
    
60.             m[i][j] = INT_MAX;
    
61.             for (k=i; k<=j-1; k++)
    
62.             {
    
63.                 // q = cost/scalar multiplications
    
64.                 q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
    
65.                 if (q < m[i][j])
    
66.                                 {
    
67.                     m[i][j] = q;
    
68.                                         s[i][j] = k;
    
69.                                 }
    
70.             }
    
71.         }
    
72.     }
    
73.     return m[1][n];
    
74. }
    
75. 
    
76. // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
    
77. int MatrixChain::MatrixChainOrderTD(int p[])
    
78. {
    
79.     for (int i = 1; i <= n; i++)
    
80.         m[i][i] = 0;
    
81.         for (int u = 0; u <= n; ++u)
    
82.                 for (int v = 0; v <= n; ++v)
    
83.                         s[u][v] = 0;
    
84. 
    
85.     int result = topdown(p, 1, n);
    
86.     return result;
    
87. }
    
88. 
    
89. void MatrixChain::traceback(int i, int j)
    
90. {
    
91.         if(i == j) return;
    
92.         traceback(i, s[i][j]);
    
93.         traceback(s[i][j]+1, j);
    
94.         std::cout << "A[" << i << ',' <<s[i][j]
    
95.                 << "] * A[" << s[i][j]+1 << ',' << j
    
96.                 << "]\n";
    
97. }
    
98. 
    
99. int MatrixChain::topdown(int p[], int i, int j)
    
100. {
     
101.         if(i != j)
     
102.         {
     
103.                 if(s[i][j]) return m[i][j];
     
104.                 m[i][j] = INT_MAX;
     
105.                 int q;
     
106.                 for(int k = i; k < j; ++k)
     
107.                 {
     
108.                         q = topdown(p, i, k) + topdown(p, k + 1, j) + p[i-1]*p[k]*p[j];
     
109.                         if (q < m[i][j])
     
110.                         {
     
111.                                 m[i][j] = q;
     
112.                                 s[i][j] = k;
     
113.                         }
     
114.                 }
     
115.         }
     
116.         return m[i][j];
     
117. }
     
118. 
     
119. int main()
     
120. {
     
121.         int arr[] = {3023, 3533, 155, 203, 2573, 3093};
     
122.         int size = sizeof(arr)/sizeof(arr[0]) - 1;
     
123.         MatrixChain mc(size);
     
124.         printf("Minimum number of multiplications is %d \n",
     
125.                        mc.MatrixChainOrder(arr));
     
126.         printf("Minimum number of multiplications is %d \n",
     
127.                        mc.MatrixChainOrderTD(arr));
     
128.         mc.traceback(1, size);
     
129.         return 0;
     
130. }

复制代码