矩阵连乘问题(递归+动态规划+备忘录法)
#include <iostream>
#include <climits>
using namespace std;
/******************** Dynamic Programming ********************/
void MatrixChain_Dynamic(int n, int *size, int **m, int **s)
{
for (int i = 1; i <= n; i++)
m[i][i] = 0; // l = 1
for (int l = 2; l <= n; l++) // l is the chain length, 自底向上！
{
int j;
for (int i = 1; i <= n + 1 - l; i++)
{
j = l + i - 1;
m[i][j] = m[i][i] + m[i + 1][j] + size[i - 1] * size[i] * size[j]; // k = i
s[i][j] = i; // k = i
int tmp;
for (int k = i + 1; k < j; k++)
{
tmp = m[i][k] + m[k + 1][j] + size[i - 1] * size[k] * size[j];
if (tmp < m[i][j])
{
m[i][j] = tmp;
s[i][j] = k;
}
}
}
}
}
/******************** Divide-Conquer ********************/
int MatrixChain_Recursive(int i, int j, int *size, int **s)
{
if (i == j)
return 0;
int result = INT_MAX;
int tmp;
for (int k = i; k < j; k++)
{
tmp = MatrixChain_Recursive(i, k, size, s) + MatrixChain_Recursive(k + 1, j, size, s) + size[i - 1] * size[k] * size[j];
if (tmp < result)
{
result = tmp;
s[i][j] = k;
}
}
return result;
}
/******************** 备忘录法 ********************/
int MatrixChain_LookUp(int i, int j, int *size, int **m, int **s)
{
if (m[i][j] > 0)
return m[i][j];
if (i == j)
return 0;
int result = INT_MAX;
int tmp;
for (int k = i; k < j; k++)
{
tmp = MatrixChain_LookUp(i, k, size, m, s) + MatrixChain_LookUp(k + 1, j, size, m, s) + size[i - 1] * size[k] * size[j];
if (tmp < result)
{
result = tmp;
s[i][j] = k;
}
}
m[i][j] = result;
return result;
}
int MemorizedMatrixChain(int i, int j, int n, int *size, int **m, int **s)
{
for (int p = 1; p <= n; p++)
for (int q = 1; q <= n; q++)
m[p][q] = 0;
return MatrixChain_LookUp(i, j, size, m, s);
}
void ConstructSolution(int i, int j, int **s)
{
if (i == j)
cout << 'A' << i;
else
{
cout << '(';
ConstructSolution(i, s[i][j], s);
ConstructSolution(s[i][j] + 1, j, s);
cout << ')';
}
}
int main()
{
int size[] = {30, 35, 15, 5, 10, 20, 25};
int n = sizeof(size) / sizeof(*size) - 1;
int **m = new int *[n + 1];
int **s = new int *[n + 1];
for (int i = 1; i <= n; i++)
{
m[i] = new int[n + 1];
s[i] = new int[n + 1];
}
/******************** Dynamic Programming ********************/
// MatrixChain_Dynamic(n, size, m, s);
// cout << m[1][n] << endl;
// cout << m[2][5] << endl;
/******************** Divide-Conquer ********************/
// cout << MatrixChain_Recursive(1, n, size, s) << endl;
// cout << MatrixChain_Recursive(2, 5, size, s) << endl;
/******************** 备忘录法 ********************/
cout << MemorizedMatrixChain(1, n, n, size, m, s) << endl;
cout << MemorizedMatrixChain(2, 5, n, size, m, s) << endl;
ConstructSolution(1, n, s);
cout << endl;
for (int i = 1; i <= n; i++)
{
delete[] m[i];
delete[] s[i];
}
delete[] m;
delete[] s;
return 0;
}