【动态规划】矩阵链乘法，最少乘法数量的组合，并输出路径（C++）

朴灿烈づ我的快乐病毒、 2022-05-09 00:40 134阅读 0赞

## 问题简述 ##

矩阵乘法，由于乘法的组合之间的先后顺序，会导致乘法数量的急剧不同。特别是矩阵规模变大的时候，因此，提前计算组合顺序，势在必行。

*  **输入：** 数字n 表示矩阵数目
 *  **输入：** n+1个数，表示的是，矩阵的长宽高度。（这里只用n+1个因为。考虑到两个矩阵之间能发送乘法，一定是中间的数是一样的，没必要重复记录）
 *  **输出：** 最小那个乘法总数。然后再输出一个S矩阵（这个矩阵是为了记录怎么划分的）。之后，通过这个S矩阵，递归得到整个乘法计算链。

**实例：**

*  输入：
 *  `6`
 *  `30 35 15 5 10 20 25`
 *  输出：

15125
    0 1 1 3 3 3
    0 0 2 3 3 3
    0 0 0 3 3 3
    0 0 0 0 4 5
    0 0 0 0 0 5
    0 0 0 0 0 0
    (A1(A2A3))((A4A5)A6)

经过验算，发现是正确的。

#include<iostream>
    using namespace std;
    #include <string>
    #include <cstring>
    #define COUNT 100
    int a[COUNT];
    int M[COUNT][COUNT];
    // M[i][j] 表示从第i个矩阵到第j个矩阵做乘法所会遇到的乘法量
    int S[COUNT][COUNT];
    string calString(int begin, int end);
    void cal(int n);
    int main() { 
    	int n;
    	cin >> n;
    	_ASSERT(n < COUNT && n >= 1);  // 添加警告
    	for (int i = 0; i < n + 1; ++i) cin >> a[i];
    	cal(n);
    	cout << M[0][n - 1] << endl;
    	for (int i = 0; i < n; ++i) { 
    		for (int j = 0; j < n; ++j) { 
    			cout << S[i][j] << " ";
    		}
    		cout << endl;
    	}
    	cout << calString(0, n-1) << endl;
    	system("pause");
    }
    
    string calString(int begin, int end) { 
    	if (begin == end) return string("A") + to_string(begin+1);
    	int k = S[begin][end];
    	string before, last;
    	if (begin == k-1) before = calString(begin, k - 1);
    	else before = string("(") + calString(begin, k - 1) + string(")");
    	if (k == end) last = calString(k, end);
    	else last = string("(") + calString(k, end) + string(")");
    	return before + last;
    }
    
    void cal(int n) { 
    	int end, min, temp;
    	for (int len = 0; len < n; ++len) { 
    		for (int begin = 0; begin + len < n; ++begin) { 
    			end = begin + len;
    			if (len == 0) M[begin][end] = 0;
    			else { 
    				for (int k = begin + 1; k <= end; ++k) { 
    					temp = M[begin][k - 1] + M[k][end] + a[begin] * a[k] * a[end + 1];
    					if (k == begin + 1 || temp < min) { 
    						min = temp;
    						S[begin][end] = k;
    					}
    				}
    				M[begin][end] = min;
    			}
    		}
    	}
    }