アルゴリズム導論15(動的計画)

//        
int cutRod(int *p,int n)
{
    if(n==0)return 0;
    int q=INT_MIN;
    for(int i=1;i<=n;++i)q=max(q,p[i]+cutRod(p,n-i));
    return q;
}

//         
int memoizedCutRodAux(int *p,int n,int *r)
{
    if(r[n]>=0)return r[n];
    int q;
    if(n==0)q=0;
    else
    {
        q=INT_MIN;
        for(int i=1;i<=n;++i)q=max(q,p[i]+memoizedCutRodAux(p,n-i,r));  
    }
    r[n]=q;
    return q;
}

int memoizedCutRod(int *p,int n)
{
    int *r=new int[n+1];
    for(int i=0;i<=n;++i)r[i]=INT_MIN;
    return memoizedCutRodAux(p,n,r);
}

//     
int bottomUpCutRod(int *p,int n)
{
    int *r=new int[n+1];
    r[0]=0;
    for(int j=1;j<=n;++j)
    {
        int q=INT_MIN;
        for(int i=1;i<=j;++j)q=max(q,p[i]+r[j-i]);
        r[j]=q;
    }
    return r[n];
}

//   
void extendedBottomUpCutRod(int *p,int n,int *r,int *s)
{
    r[0]=0;
    for(int j=1;j<=n;++j)
    {
        int q=INT_MIN;
        for(int i=1;i<=j;++j)
        {
            if(q<p[i]+r[j-i]) { q=p[i]+r[j-i]; s[j]=i; } } r[j]=q; } } void printCutRodSolution(int *p,int n) { int *r=new int[n+1]; int *s=new int[n+1]; extendedBottomUpCutRod(p,n,r,s); while(n>0)
    {
        cout<<s[n]<<' ';
        n-=s[n];
    }
}

//    
void matrixMultiply(vector<vector<int> > A,vector<vector<int> > B,vector<vector<int> > &C)
{
    if(A[0].size()!=B.size())return;
    for(int i=0;i<A.size();++i)
    {
        for(int j=0;j<B[0].size();++j)
        {
            C[i][j]=0;
            for(int k=0;k<A[0].size();++k)C[i][j]+=A[i][k]*B[k][j];
        }
    }
}

//     
void matrixChainOrder(vector<int> p,vector<vector<int> > &m,vector<vector<int> > &s)
{
    int n=p.size()-1;
    for(int i=1;i<=n;++i)m[i][i]=0;
    for(int l=2;l<=n;++l)
    {
        for(int i=1;i<=n-l+1;++i)
        {
            int j=i+l-1;
            m[i][j]=INT_MAX;
            for(int k=i;k<=j-1;++k)
            {
                int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j])
                {
                    m[i][j]=q;
                    s[i][j]=k;
                }
            }
        }
    }
}

void printOptimalParens(vector<vector<int> > s,int i,int j)
{
    if(i==j)cout<<"A"<<i;
    else
    {
        cout<<'(';
        printOptimalParens(s,i,s[i][j]);
        printOptimalParens(s,s[i][j]+1,j);
        cout<<')';
    }
}

//  
int recursiveMatrixChain(vector<int> p,int i,int j,vector<vector<int> > &m)
{
    if(i==j)return 0;
    m[i][j]=INT_MAX;
    for(int k=i;k<=j-1;++k)
    {
        int q=recursiveMatrixChain(p,i,k,m)+recursiveMatrixChain(p,k+1,j,m)+p[i-1]*p[k]*p[j];
        if(q<m[i][j])m[i][j]=q;
    }
    return m[i][j];
}

//  
int lookupChain(vector<vector<int> > m,vector<int> p,int i,int j)
{
    if(m[i][j]<INT_MAX)return m[i][j];
    if(i==j)m[i][j]=0;
    else
    {
        for(int k=i;k<=j-1;++k)
        {
            int q=lookupChain(m,p,i,k)+lookupChain(m,p,k+1,j)+p[i-1]*p[k]*p[j];
            if(q<m[i][j])m[i][j]=q;
        }
    }
    return m[i][j];
}

int memoizedMatrixChain(vector<int> p)
{
    int n=p.size()-1;
    vector<vector<int> > m(n+1,vector<int>(n+1,INT_MAX));
    return lookupChain(m,p,1,n);
}

void LCSLength(vector<char> X,vector<char> Y,vector<vector<int> > &b,vector<vector<int> > &c)
{
    int m=X.size();
    int n=Y.size();
    for(int i=1;i<=m;++i)c[i][0]=0;
    for(int j=0;j<=n;++j)c[0][j]=0;
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(X[i]==Y[j])
            {
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=1;
            }
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];
                b[i][j]=2;
            }
            else
            {
                c[i][j]=c[i][j-1];
                b[i][j]=3;
            }
        }
    }
}

void printLCS(vector<vector<int> > b,vector<char> X,int i,int j)
{
    if(i==0||j==0)return;
    if(b[i][j]==1)
    {
        printLCS(b,X,i-1,j-1);
        cout<<X[i]<<' ';
    }
    else if(b[i][j]==2)printLCS(b,X,i-1,j);
    else printLCS(b,X,i,j-1);
}

//p[1..n]
//q[0..n]
//e[1..n+1,0..n]
//w[1..n+1,0..n]
//root[1..n,1..n]
//      O(n^3)
void optimalBST(vector<int> p,vector<int> q,int n,vector<vector<int> > &e,vector<vector<int> > &w,vector<vector<int> > &root)
{
    for(int i=1;i<=n+1;++i)e[i][i-1]=w[i][i-1]=q[i-1];
    for(int l=1;l<=n;++l)
    {
        for(int i=1;i<=n-l+1;++i)
        {
            int j=i+l-1;
            e[i][j]=INT_MAX;
            w[i][j]=w[i][j-1]+p[j]+q[j];
            for(int r=i;r<=j;++r)
            {
                int t=e[i][r-1]+e[r+1][j]+w[i][j];
                if(t<e[i][j])
                {
                    e[i][j]=t;
                    root[i][j]=r;
                }
            }
        }

    }
}

//  ，      O(n^2)。
void optimalBST(vector<int> p,vector<int> q,int n,vector<vector<int> > &e,vector<vector<int> > &w,vector<vector<int> > &root)
{
    for(int i=1;i<=n+1;++i)e[i][i-1]=w[i][i-1]=q[i-1];
    for(int l=1;l<=n;++l)
    {
        for(int i=1;i<=n-l+1;++i)
        {
            int j=i+l-1;
            e[i][j]=INT_MAX;
            w[i][j]=w[i][j-1]+p[j]+q[j];    
            //root[i][j-1]<=root[i][j]<=root[i+1][j]
            if(i==j)
            {
                int t=e[i][r-1]+e[r+1][j]+w[i][j];
                if(t<e[i][j])
                {
                    e[i][j]=t;
                    root[i][j]=i;
                }
            }
            else
            {
                for(int r=root[i][j-1];r<=root[i+1][j];++r)
                {
                    int t=e[i][r-1]+e[r+1][j]+w[i][j];
                    if(t<e[i][j])
                    {
                        e[i][j]=t;
                        root[i][j]=r;
                    }
                }
            }
        }
    }
}

const int N=100;

struct ENode
{
    int val,w;
    ENode *next;
};

struct VNode
{
    ENode *next;
};

struct Graph    
{    
    VNode Adj[N];    
    int VNum,ENum;    
};    

void longestPathAux(Graph G,int u,int t,int *dist,int *next)
{
    if(u==t)dist[u]=0;
    else if(next[u]==0)
    {
        for(ENode *p=G.Adj[u].next;p;p=p->next)
        {
            int v=p->val,w=p->w;
            longestPathAux(G,v,t,dist,next);
            if(w+dist[v]>dist[u])
            {
                dist[u]=w+dist[v];
                next[u]=v;
            }
        }
    }
}

void printPath(int s,int t,int *next)
{
    int u=s;
    cout<<u;
    while(u!=t)
    {
        cout<<"->"<<next[u];
        u=next[u];
    }
}

void longestPathMain(Graph G,int s,int t)
{
    int n=G.VNum;
    int *dist=new int[n+1],*next=new int[n+1];
    for(int i=1;i<=n;++i)
    {
        dist[i]=INT_MIN;
        next[i]=-1;
    }
    longestPathAux(G,s,t,dist,next);
    if(dist[s]==INT_MIN)cout<<"No path exits"<<endl;
    else
    {
        cout<<"The weight of the longest path is "<<dist[s]<<endl;
        printPath(s,t,next);
    }
    delete [] dist,next;
}