#include<iostream>
#include<string>
#include<vector>
#include<memory.h>
using namespace std;

string s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
string s2 = "CACCCCTAAGGTACCTTTGGTTC";

vector<vector<int> > memo( 100,vector<int>(100,0));
int LCS( int len1 , int len2 )
{
    if( len1 < 0 || len2 < 0 )
        return 0;
    
    if( memo[len1][len2] != 0 )
        return memo[len1][len2];
    if( s1[len1] == s2[len2] )
    {
        memo[len1][len2] = 1 + LCS( len1-1 ,len2-1 );
    }
    else
        memo[len1][len2] = max( LCS(len1-1,len2) , LCS(len1,len2-1) );
    return memo[len1][len2];
}
int main()
{
    cout << LCS( s1.length()-1 , s2.length()-1 ) << endl;
    return 0;
}

#include<iostream>
#include<memory.h>
using namespace std;

string s1 = "AAACCGTGAGTTATTCGTTCTAGAA";
string s2 = "CACCCCTAAGGTACCTTTGGTTC";
//string s1 = "357486782";
//string s2 = "13456778";
int memo[100][100];
int main()
{
    memset( memo , 0 , sizeof(memo) );
    int i , j ;
    for( i = 0 ; i < s1.length() ; i ++ )
    {
        for( j = 0 ; j < s2.length() ; j ++ )
        {
            if( s1[i] == s2[j] )
            {                       
                if( i == 0 || j == 0 )  //³ö½çÁË 
                    memo[i][j] = 1;
                else
                    memo[i][j] = 1 + memo[i-1][j-1];
            }
            else
            {
                if( i == 0 || j == 0 )
                    memo[i][j] = 0;
                else
                    memo[i][j] = max( memo[i-1][j] , memo[i][j-1] );
            }
                
        }
    }
    cout << memo[s1.length()-1][s2.length()-1] << endl;
    return 0;
}

以上是自己写的LCS的两种解决方式  麻烦波波老师帮看看写的对不对。