最长公共子序列，即给出两个序列，给出最长的公共序列，例如：
序列1 understand
序列2 underground
最长公共序列undernd，长度为7
一般这类问题很适合使用动态规划，其动态规划描述如下：
设序列1为s,序列2为t，则
if s[i+1]==t[j+1] dp[i+1][j+1]=dp[i][j]+1
else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
代码如下：
#pragma once
#include <string> using std::string; string LCS(string s, string t)
{
const int MAX_N = ;
int dp[MAX_N][MAX_N];
string rec[MAX_N][MAX_N]; for (int i = ;i < s.size();++i)
{
for (int j = ;j < t.size();++j)
{
dp[i][j] = ;
rec[i][j].clear();
}
}
for (int i = ;i < s.size();++i)
{
for (int j = ;j < t.size();++j)
{
if (s[i] == t[j])
{
dp[i + ][j + ] = dp[i][j] + ;
rec[i + ][j + ] = rec[i][j] + s[i];
}
else
{
if (dp[i][j + ] > dp[i + ][j])
{
dp[i + ][j + ] = dp[i][j + ];
rec[i + ][j + ] = rec[i][j + ];
}
else
{
dp[i + ][j + ] = dp[i + ][j];
rec[i + ][j + ] = rec[i + ][j];
}
}
}
}
return rec[s.size()][t.size()];
}
以上为backward approach（forward search），如果选择后溯，则需要记录何时存储数组，何时直接使用已有数据。