算法1：动态规划

       动态规划的基本思想是：将求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。与分治法的区别是，适合用动态规划解决的问题，经分解得到的子问题往往不是相互独立的。动态规划将问题分解成子问题，但是子问题不相互独立，而是彼此依赖，相互提供帮助，很好的利用了子问题的结构信息。

动态规划的步骤是：

1.找出最优解的特征，并刻画其结构特征；

2.递归地定义最优值；

3.以自底向上的方式计算出最优值；

4.根据计算最优值的时得到的信息，构造最优解。

动态规划算法的有效性依赖于两个最重要的性质：最优子结构性质和重叠子问题性质。

栗子1，矩阵连乘问题。

//动态规划——矩阵连乘问题
#include<iostream>
#include<cstring> 

using namespace std;
int p[7]={30,35,15,5,10,20,25};//6个矩阵
int m[6][6];//存放计算量的矩阵
int s[6][6];//存放分割点的矩阵

void matrixChain()//第三步：计算最优值（前面两步没法再代码中体现，是构思的过程）
                  //生成断点矩阵的函数，计算出最优值,返回s矩阵
{
    int length=6;
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    for(int r=2;r<=length;r++)//r表示的是计算的范围，开始只计算两个矩阵的计算量，然后依次计算3个，4个一直到目标的6个
                              //这是动态规划自底向上的体现，从最小的单位开始计算
    {
        for(int i=1;i<=length-r+1;i++)//i，j分别表示当前所计算的范围
        {
            int j=i+r-1;
            m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i-1]*p[j];//因为后面要求最优值，所以这里其实是随便求一个值
            s[i][j]=i;
            for(int k=i+1;k<j;k++)//范围内优化，找到最小的值
            {
                int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(temp<m[i][j])
                {
                    m[i][j]=temp;
                    s[i][j]=k;
                }
            }
        }
    }
}
void TraceBack(int i,int j)//第4步：构造最优解。输入s矩阵和想要求解的范围，输出最佳的括号方案
{
    if(i==j)
    {
        cout<<"M"<<"["<<i<<"]";
        return;
    }
    cout<<"(";
    TraceBack(i,s[i][j]);
    TraceBack(s[i][j]+1,j);
    cout<<")";
}
int main()
{
    matrixChain();
    TraceBack(1,6);
    cout<<m[1][6]<<endl;
    return 0;
}

 栗子2：最长公共子序列

//动态规划-最长公共子序列
#include<iostream>
using namespace std;
char x[8]={'Z','A','B','C','B','D','A','B'};//函数中根本不会计算x[0]和y[0],这两个位置的字母只是为了占坑用
char y[7]={'Z','B','D','C','A','B','A'};
int c[8][7]={0};//子序列的长度
int b[8][7]={0};//子序列以哪种方式可以找到它最长子序列。递归方式
//计算最优值
void lcsLength()
{
    int m=7;//第一个序列的长度
    int n=6;//第二个序列的长度
    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 lcs(int i,int j)//输出子序列和其长度
{
    if(i==0||j==0)
    return;
    if(b[i][j]==1)
    {
        lcs(i-1,j-1);
        cout<<x[i];
    }
    else
    {
        if(b[i][j]==2)
        {
            lcs(i-1,j);
        }
        else
        {
            lcs(i,j-1);
        }
        
    }
    
 

}
int main()
{
    lcsLength();
    lcs(7,6);
    cout<<c[7][6]<<endl;//子序列的最大长度
    return 0;
}

 在牛客上提交的版本，牛客只需要输出最长公共子序列的长度

//动态规划-最长公共子序列
#include<iostream>
using namespace std;
void lcsLength(char x[],char y[],int m,int n)
{
    int c[m+1][n+1];//子序列的长度
    for(int i=0;i<m+1;i++)
    {
        for(int j=0;j<n+1;j++)
            c[i][j]=0;
    }
    int b[m+1][n+1];//子序列以哪种方式可以找到它最长子序列。递归方式
    for(int i=0;i<m+1;i++)
    {
        for(int j=0;j<n+1;j++)
            b[i][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;
                }
                 
            }
             
        }
    }
    cout<<c[m][n]<<endl;
}
void lcs()
{
    char a[1024];
    a[0]='Z';
    char b[1024];
    b[0]='Z';
    string str1;
     string str2;
    while(cin>>str1>>str2)
    {
        for(int i=0;i<str1.size();i++)
            a[i+1]=str1[i];
        for(int i=0;i<str2.size();i++)
            b[i+1]=str2[i];
        lcsLength(a,b,str1.size(),str2.size());
    }
}
int main()
{
    lcs();
    return 0;
}