问题

给出两个序列,求出一个序列使得同时是和的子序列，且的长度最大

解析

给出一个动态规划的做法
令表示序列的前项和序列的前项的最长公共子序列
那么就有
最优子问题证明

• 已知是序列的前项和序列的前项的最长公共子序列
  • 当时，假设存在,则即存在与已知不符，假设不成立
  • 当时，假设存在,则与已知不符，假设不成立，情况同理可证

    设计

    const int maxn = 1010;
    int dp[maxn][maxn];
    int s[maxn], t[maxn];
    int ds[maxn][maxn], dt[maxn][maxn];
    int main()
    {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(dp, 0, sizeof dp);
    memset(ds, 0, sizeof ds);
    memset(dt, 0, sizeof dt);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", s + i);
    }
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", t + i);
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (s[i] == t[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i - 1][j] > dp[i][j - 1])
                {
                    ds[i][j] = 1;
                }else
                {
                    dt[i][j] = 1;
                }
            }
        }
    }
    printf("%d\n", dp[n][m]);
    stack<int> stk;
    int l = n, r = m;
    while (l > 0 && r > 0)
    {
        if (s[l] == t[r])
        {
            stk.push(s[l]);
            --l;
            --r;
        }else
        {
            l -= ds[l][r];
            r -= dt[l][r];
        }
    }
    while(!stk.empty())
    {
        printf("%d ", stk.top());
        stk.pop();
    }
    }
    //16 17
    //24 13 29 24 8 23 28 24 17 8 5 3 24 22 10 8 
    //9 22 21 17 23 30 25 17 17 22 19 21 23 30 11 26 12 

分析

很显然，算法总共有两重循环，总复杂度

源码

传送门