每日一题之矩阵链乘法（动态规划实现）

Solution.h

#ifndef _SOLUTION_H_
#define _SOLUTION_H_

#include <vector>

using std::vector;

class Matrix
{
public:
Matrix(vector<vector<double>>&& matrix);

Matrix(int rows, int cols);

int getRows() const ;

int getColumns() const;

private:
int _rows;
int _columns;
};

class Solution
{
public:
Solution();

// 构造矩阵链
void push(Matrix&& m);

// 最小代价
void optSol();

private:
// 获取最佳完全括号化方案
int getOptSol(int i, int j);

// 分解方案，中序遍历打印
void printInOrder(int i, int j);

// 获取矩阵链的长度
int getLen();

// 初始化划分矩阵
void initOpt();

private:
// 存储矩阵链
vector<Matrix> _chain;

// 存储Ai –> Aj的最小开销
vector<vector<int>> _optMatrix;

// 存储Ai –> Aj 的最佳划分方法的中间结点
vector<vector<int>> _optSegment;
};

#endif

Solution.cc

#include "Solution.h"
#include <iostream>

using std::cout;
using std::endl;

Matrix::Matrix(vector<vector<double>>&& matrix)
:_rows(matrix.size())
,_columns(matrix[0].size())
{
if (_columns == 0)
_rows = 0;
};

Matrix::Matrix(int rows, int cols)
:_rows(rows)
,_columns(cols)
{

}

int Matrix::getRows() const
{
return _rows;
};

int Matrix::getColumns() const
{
return _columns;
};

Solution::Solution()
:_chain()
,_optMatrix()
,_optSegment()
{
}

// 构造矩阵链
void Solution::push(Matrix&& m)
{
_chain.push_back(std::move(m));
}

// 获取矩阵链的长度
int Solution::getLen()
{
return _chain.size();
}

// 初始化划分矩阵
void Solution::initOpt()
{
int size = getLen();

for (int idx = 0; idx < size; ++idx)
{
_optMatrix.push_back(vector<int>(size, 0));
_optSegment.push_back(vector<int>(size, 0));
}
}

// 获取最佳完全括号化方案
int Solution::getOptSol(int i, int j)
{
// 动态规划，避免子问题重复计算
if (_optMatrix[i][j] != 0)
return _optMatrix[i][j];

// 单个矩阵不需计算
if (i == j)
return 0;

// 矩阵链的矩阵个数为2，直接返回两个矩阵相乘的结果
int cost;
if (i + 1 == j)
{
cost = _chain[i].getRows() * _chain[i].getColumns() * _chain[j].getColumns();
_optMatrix[i][j] = cost;
_optSegment[i][j] = i;
return _optMatrix[i][j];
}

// 矩阵链的矩阵个数大于2，将矩阵链分成2段，将每段视
// 为一个矩阵，选择最小代价的分割方法
for (int k = i; k < j; ++k)
{
int left = getOptSol(i, k);
int right = getOptSol(k + 1, j);
cost = left + right + _chain[i].getRows() * _chain[k].getColumns() * _chain[j].getColumns();

if (_optMatrix[i][j] == 0)
{
_optMatrix[i][j] = cost;
_optSegment[i][j] = k;
}
else
{
if (_optMatrix[i][j] > cost)
{
_optMatrix[i][j] = cost;
_optSegment[i][j] = k;
}
}
}
return _optMatrix[i][j];
}

// 分解方案，中序遍历打印
void Solution::printInOrder(int i, int j)
{
if (i == j)
{
cout << "A" << i + 1;
return;
}

int pivot = _optSegment[i][j];
cout << "(";
printInOrder(i, pivot);
printInOrder(pivot + 1, j);
cout << ")";
};

// 最小代价
void Solution::optSol()
{
int res = -1;
int size = getLen();
// 检验矩阵链是否合法
for (int idx = 0; idx < size – 1; ++idx)
{
if (_chain[idx].getColumns() != _chain[idx + 1].getRows())
{
cout << "矩阵链无效！" << endl;
return;
}
}

initOpt();
res = getOptSol(0, size – 1);
cout << "optimum solution's cost is " << res << endl;
cout << "optimum segmentation is : ";
printInOrder(0, size – 1);
cout << endl;
}

test.cc

#include "Solution.h"
#include <iostream>

using std::cout;
using std::endl;

void test()
{
Matrix m(vector<vector<double>>({{}}));
cout << m.getRows() << ", " << m.getColumns() << endl;

Solution s;
s.push(Matrix(30, 35));
s.push(Matrix(35, 15));
s.push(Matrix(15, 5));
s.push(Matrix(5, 10));
s.push(Matrix(10, 20));
s.push(Matrix(20, 25));

s.optSol();
}

int main(int argc, char** argv)
{
test();
return 0;
}