This is the 7th day of my participation in the August More Text Challenge

Matrix LianCheng

1. The train of thought:

Use memo method to solve.

The memo method uses tables to save the answers to solved subproblems, so that the next time you need to solve the subproblem, you can simply view the solution to the subproblem without recalculating. The memo method creates a record entry for each subproblem, which, when initialized, stores a special value indicating that the subproblem has not been solved. In the process of solving, for each subproblem solved, first check its corresponding record item. If the record item stores the special value saved during initialization, it indicates that the problem is encountered for the first time. At this time, the solution of the sub-problem is calculated and saved in the corresponding record item for future reference. If the value stored in the record item is not the special value stored during initialization, it indicates that the subproblem has been calculated, and the corresponding record item stores the solution to the subproblem. Instead of recalculating, the solution to the subproblem can be retrieved from the record entry.

#include<iostream>
using namespace std;
// Memo method for dynamic programming

const int L=7;

int lookupChain(int i,int j,int **m,int **s,int *p);
int MemoizeMatrixChain(int n,int **m,int **s,int *p);

void Traceback(int i,int j,int **s);// Construct the optimal solution

int main(a){
    int p[L]={30.35.15.5.10.20.25};//30x35 35x15 15x5.....

    int **s =new int *[L];
    int **m =new int *[L];
    for(int i=0; i<L; i++){ s[i]=new int[L];
        m[i]=new int[L];
    }

    cout<<"The minimum number of computations of the matrix is :"<<MemoizeMatrixChain(L- 1,m,s,p)<<endl;
    cout<<"The optimal calculation order of the matrix is:"<<endl;
    Traceback(1,L- 1,s);
    system("pause");
    return 0;
}

int MemoizeMatrixChain(int n,int **m,int **s,int *p)
{
    for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) { m[i][j]=0;// Initialize the array}}return lookupChain(1,n,m,s,p);
}

int lookupChain(int i,int j,int **m,int **s,int *p)
{
    if(m[i][j]>0)// If M[I][j] is not 0, the array value is updated
    {
        return m[i][j];
    }
    if(i==j)// Single matrix, multiplication is 0
        return 0;

    int u=lookupChain(i,i,m,s,p)+lookupChain(i+1,j,m,s,p)+p[i- 1]*p[i]*p[j];
    s[i][j]=i;// the s array is used to record delimited k values
    for(int k=i+1; k<j; k++) {int t=lookupChain(i,k,m,s,p)+lookupChain(k+1,j,m,s,p)+p[i- 1]*p[k]*p[j];
         if(t<u){// Update the minimum multiplication
             u=t;
             s[i][j] = k;
         }
    }
    m[i][j] = u;
    return u;
}

// Get each parenthesis split position according to the s array traceback
void Traceback(int i,int j,int **s)
{
    if(i==j) return;
    Traceback(i,s[i][j],s);
    Traceback(s[i][j]+1,j,s);
    cout<<"Multiply A"<<i<<","<<s[i][j];
    cout<<"and A"<<(s[i][j]+1) < <","<<j<<endl;
}
Copy the code