LCS 最長公共子序列

兩個串a1 a2 a3···an   b1 b2 b3···bm

這倆的最長公共子序列為c1 c2 c3···ck

dp[i][j]表示串a長度為i時和串b長度為j時的最長公共子序列的長度

 1、若an == bn，則ck = an，即c1 c2 c3···c(k-1)為a1 a2 a3···a(n-1) 和 b1 b2 b3···b(m-1)的最長公共子序列，同理第i，j個位置，dp[i][j] = dp[i - 1][j - 1] + 1;

2、若an != bn ，若ck != an,  即c1 c2 c3···c(k-1)為a1 a2 a3···a(n-1) 和 b1 b2 b3···b(m)的最長公共子序列，同理第i，j個位置，dp[i][j] = dp[i - 1][j];

3、若an != bn ，若ck != bm,  即c1 c2 c3···c(k-1)為a1 a2 a3···an 和 b1 b2 b3···b(m - 1)的最長公共子序列，同理第i，j個位置，dp[i][j] = dp[i][j - 1];

綜上

if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);      

int dp[1010][1010];
int main()
{


    string str1, str2;
    while(cin >> str1 >> str2)
    {
        mem(dp, 0);
        int len1 = str1.size();
        int len2 = str2.size();
        for(int i = 0; i < len1; i++)
            for(int j = 0; j < len2; j++)
                if(str1[i] == str2[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        cout << dp[len1][len2] << endl;
    }


    return 0;
}      

自己選擇的路，跪着也要走完。朋友們，雖然這個世界日益浮躁起來，隻要能夠為了當時純粹的夢想和感動堅持努力下去，不管其它人怎麼樣，我們也能夠保持自己的本色走下去。