Solution.h<\/p>\n
#ifndef _SOLUTION_H_
\n#define _SOLUTION_H_<\/p>\n
#include <vector><\/p>\n
using std::vector;<\/p>\n
class Matrix
\n{
\npublic:
\n Matrix(vector<vector<double>>&& matrix);<\/p>\n
Matrix(int rows, int cols);<\/p>\n
int getRows() const ;<\/p>\n
int getColumns() const;<\/p>\n
private:
\n int _rows;
\n int _columns;
\n};<\/p>\n
class Solution
\n{
\npublic:
\n Solution();<\/p>\n
\/\/ \u6784\u9020\u77e9\u9635\u94fe
\n void push(Matrix&& m);<\/p>\n
\/\/ \u6700\u5c0f\u4ee3\u4ef7
\n void optSol();<\/p>\n
private:
\n \/\/ \u83b7\u53d6\u6700\u4f73\u5b8c\u5168\u62ec\u53f7\u5316\u65b9\u6848
\n int getOptSol(int i, int j);<\/p>\n
\/\/ \u5206\u89e3\u65b9\u6848，\u4e2d\u5e8f\u904d\u5386\u6253\u5370
\n void printInOrder(int i, int j);<\/p>\n
\/\/ \u83b7\u53d6\u77e9\u9635\u94fe\u7684\u957f\u5ea6
\n int getLen();<\/p>\n
\/\/ \u521d\u59cb\u5316\u5212\u5206\u77e9\u9635
\n void initOpt();<\/p>\n
private:
\n \/\/ \u5b58\u50a8\u77e9\u9635\u94fe
\n vector<Matrix> _chain;<\/p>\n
\/\/ \u5b58\u50a8Ai –> Aj\u7684\u6700\u5c0f\u5f00\u9500
\n vector<vector<int>> _optMatrix;<\/p>\n
\/\/ \u5b58\u50a8Ai –> Aj \u7684\u6700\u4f73\u5212\u5206\u65b9\u6cd5\u7684\u4e2d\u95f4\u7ed3\u70b9
\n vector<vector<int>> _optSegment;
\n};<\/p>\n
#endif<\/p>\n
Solution.cc<\/p>\n
#include "Solution.h"
\n#include <iostream><\/p>\n
using std::cout;
\nusing std::endl;<\/p>\n
Matrix::Matrix(vector<vector<double>>&& matrix)
\n:_rows(matrix.size())
\n,_columns(matrix[0].size())
\n{
\n if (_columns == 0)
\n _rows = 0;
\n};<\/p>\n
Matrix::Matrix(int rows, int cols)
\n:_rows(rows)
\n,_columns(cols)
\n{<\/p>\n
}<\/p>\n
int Matrix::getRows() const
\n{
\n return _rows;
\n};<\/p>\n
int Matrix::getColumns() const
\n{
\n return _columns;
\n};<\/p>\n
Solution::Solution()
\n:_chain()
\n,_optMatrix()
\n,_optSegment()
\n{
\n}<\/p>\n
\/\/ \u6784\u9020\u77e9\u9635\u94fe
\nvoid Solution::push(Matrix&& m)
\n{
\n _chain.push_back(std::move(m));
\n}<\/p>\n
\/\/ \u83b7\u53d6\u77e9\u9635\u94fe\u7684\u957f\u5ea6
\nint Solution::getLen()
\n{
\n return _chain.size();
\n}<\/p>\n
\/\/ \u521d\u59cb\u5316\u5212\u5206\u77e9\u9635
\nvoid Solution::initOpt()
\n{
\n int size = getLen();<\/p>\n
for (int idx = 0; idx < size; ++idx)
\n {
\n _optMatrix.push_back(vector<int>(size, 0));
\n _optSegment.push_back(vector<int>(size, 0));
\n }
\n}<\/p>\n
\/\/ \u83b7\u53d6\u6700\u4f73\u5b8c\u5168\u62ec\u53f7\u5316\u65b9\u6848
\nint Solution::getOptSol(int i, int j)
\n{
\n \/\/ \u52a8\u6001\u89c4\u5212，\u907f\u514d\u5b50\u95ee\u9898\u91cd\u590d\u8ba1\u7b97
\n if (_optMatrix[i][j] != 0)
\n return _optMatrix[i][j];<\/p>\n
\/\/ \u5355\u4e2a\u77e9\u9635\u4e0d\u9700\u8ba1\u7b97
\n if (i == j)
\n return 0;<\/p>\n
\/\/ \u77e9\u9635\u94fe\u7684\u77e9\u9635\u4e2a\u6570\u4e3a2，\u76f4\u63a5\u8fd4\u56de\u4e24\u4e2a\u77e9\u9635\u76f8\u4e58\u7684\u7ed3\u679c
\n int cost;
\n if (i + 1 == j)
\n {
\n cost = _chain[i].getRows() * _chain[i].getColumns() * _chain[j].getColumns();
\n _optMatrix[i][j] = cost;
\n _optSegment[i][j] = i;
\n return _optMatrix[i][j];
\n }<\/p>\n
\/\/ \u77e9\u9635\u94fe\u7684\u77e9\u9635\u4e2a\u6570\u5927\u4e8e2，\u5c06\u77e9\u9635\u94fe\u5206\u62102\u6bb5，\u5c06\u6bcf\u6bb5\u89c6
\n \/\/ \u4e3a\u4e00\u4e2a\u77e9\u9635，\u9009\u62e9\u6700\u5c0f\u4ee3\u4ef7\u7684\u5206\u5272\u65b9\u6cd5
\n for (int k = i; k < j; ++k)
\n {
\n int left = getOptSol(i, k);
\n int right = getOptSol(k + 1, j);
\n cost = left + right + _chain[i].getRows() * _chain[k].getColumns() * _chain[j].getColumns();<\/p>\n
if (_optMatrix[i][j] == 0)
\n {
\n _optMatrix[i][j] = cost;
\n _optSegment[i][j] = k;
\n }
\n else
\n {
\n if (_optMatrix[i][j] > cost)
\n {
\n _optMatrix[i][j] = cost;
\n _optSegment[i][j] = k;
\n }
\n }
\n }
\n return _optMatrix[i][j];
\n}<\/p>\n
\/\/ \u5206\u89e3\u65b9\u6848，\u4e2d\u5e8f\u904d\u5386\u6253\u5370
\nvoid Solution::printInOrder(int i, int j)
\n{
\n if (i == j)
\n {
\n cout << "A" << i + 1;
\n return;
\n }<\/p>\n
int pivot = _optSegment[i][j];
\n cout << "(";
\n printInOrder(i, pivot);
\n printInOrder(pivot + 1, j);
\n cout << ")";
\n};<\/p>\n
\/\/ \u6700\u5c0f\u4ee3\u4ef7
\nvoid Solution::optSol()
\n{
\n int res = -1;
\n int size = getLen();
\n \/\/ \u68c0\u9a8c\u77e9\u9635\u94fe\u662f\u5426\u5408\u6cd5
\n for (int idx = 0; idx < size – 1; ++idx)
\n {
\n if (_chain[idx].getColumns() != _chain[idx + 1].getRows())
\n {
\n cout << "\u77e9\u9635\u94fe\u65e0\u6548！" << endl;
\n return;
\n }
\n }<\/p>\n
initOpt();
\n res = getOptSol(0, size – 1);
\n cout << "optimum solution's cost is " << res << endl;
\n cout << "optimum segmentation is : ";
\n printInOrder(0, size – 1);
\n cout << endl;
\n}<\/p>\n
test.cc<\/p>\n
#include "Solution.h"
\n#include <iostream><\/p>\n
using std::cout;
\nusing std::endl;<\/p>\n
void test()
\n{
\n Matrix m(vector<vector<double>>({{}}));
\n cout << m.getRows() << ", " << m.getColumns() << endl;<\/p>\n
Solution s;
\n s.push(Matrix(30, 35));
\n s.push(Matrix(35, 15));
\n s.push(Matrix(15, 5));
\n s.push(Matrix(5, 10));
\n s.push(Matrix(10, 20));
\n s.push(Matrix(20, 25));<\/p>\n
s.optSol();
\n}<\/p>\n
int main(int argc, char** argv)
\n{
\n test();
\n return 0;
\n}<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb61\u6b21\u3002\u3010\u4ee3\u7801\u3011\u6bcf\u65e5\u4e00\u9898\u4e4b\u77e9\u9635\u94fe\u4e58\u6cd5\uff08\u52a8\u6001\u89c4\u5212\u5b9e\u73b0\uff09<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2865,1578,1649],"topic":[],"class_list":["post-45510","post","type-post","status-publish","format-standard","hentry","category-server","tag-2865","tag-1578","tag-1649"],"yoast_head":"\n