dp:
#include<iostream>
#include<vector>
#include <climits>
#include <cfloat>
#include<iomanip>
using namespace std;
void dp(vector<vector<int>>& m, vector<vector<int>>& s,vector<int>&p)
{
int n = m.size() - 1;
int j, min, t;
for (int i = 1; i < m.size(); i++)
m[i][i] = 0;
for (int r = 2; r <= n; r++)
{
for (int i = 1; i <= n - r + 1; i++)
{
j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
s[i][j] = i;
for (int k = i + 1; k < j; k++)
{
t= m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (m[i][j] >t)
{
m[i][j]=t;
s[i][j] = k;
}
}
}
}
}
void visit(vector<vector<int>>& m,int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << setw(5)<<m[i][j] << ' ';
cout << endl;
}
}
int main()
{
int n = 6;
vector<vector<int>>m(n+1, vector<int>(n+1));
vector<vector<int>>s(n+1, vector<int>(n+1));
vector<int>p(n + 1);
int a[7] = { 30,35,15,5,10,20,25 };
for (int i = 0; i <= n; i++)
p[i] =a[i] ;
dp(m, s, p);
cout << "-------" << endl;
cout << "m:" << endl;
visit(m,n);
cout << "------" << endl;
cout << "s:" << endl;
visit(s,n);
return 0;
}
备忘录方法：
int lookupchain(int i, int j,vector<vector<int>>&s, vector<vector<int>>& m,vector<int>&p)
{
if (i==j)
return 0;
if (m[i][j] > 0)
return m[i][j];
int u = lookupchain(i+1,j,s,m,p) + p[i - 1] * p[i] * p[j];
s[i][j] = i;
for (int k=i+1; k < j; k++)
{
int t = lookupchain(i,k, s, m, p) + lookupchain(k+1,j, s, m, p) + p[i - 1] * p[k] * p[j];
if (t < u)
{
u = t;
s[i][j] = k;
}
}
m[i][j] = u;
return u;
}
void MemorizesdMatrix(int n, vector<vector<int>>& m, vector<vector<int>>& s, vector<int>& p)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
m[i][j] = 0;
s[i][j] = 0;
}
int min = lookupchain(1, n, s, m, p);
cout << min << endl;
}
