题目传送门：POJ 1934 Trip

题意：

求两个序列的最长公共子序列（LCS），LCS可能不唯一，按字典序输出所有LCS。

思路：

先按动态规划的思路，定义 数组a1~ai 与 数组b1~bi 的最长公共子序列长度为$dp[i][j]$，则有：

$$
dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & \text {if($a[i]==a[j]$) } \max(dp[i-1][j],dp[i][j-1]), & \text{else} \end{cases}
$$

然后根据dp值，递归倒序求出LCS，代码如下（会超时）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
const int N=110;
set<string>ans;
char a[N],b[N];
int n,m,dp[N][N];
void get_LCS(int i,int j,string s) 
// i为数组a下标，j为数组b下标，s为当前搜索到的公共子序列(逆序)
{
    if(i==0||j==0)
    {
        ans.insert(s.assign(s.rbegin(),s.rend()));
        return;
    }
    if(a[i]==b[j])
    {
        get_LCS(i-1,j-1,s+a[i]);
    }
    else
    {
        if(dp[i][j]==dp[i-1][j])
        {
            get_LCS(i-1,j,s);
        }
        if(dp[i][j]==dp[i][j-1])
        {
            get_LCS(i,j-1,s);
        }
    }
}
void get_dp()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            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 main()
{
    ios::sync_with_stdio(false);
    cin>>a+1>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    get_dp();
    get_LCS(n,m,"");
    for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
        printf("%s\n",(*it).c_str());
    return 0;
}

以上代码超时，原因在于重复搜索了LCS，需要剪枝！