问题

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

解析

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

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

      设计

      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 

分析

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

源码

传送门