最长公共子序列法做，但我感觉相对于LIS不太好理解，先敲个代码

状态转移函数

A[i] = A[j], dp[i] = max(dp[i - 1][j], dp[i][j - 1]) + 1 A[i] != A[j], dp[i] = max(dp[i - 1][j], dp[i] [j - 1])

代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int maxc = 210;
  5. const int maxn = 10010;
  6. int A[maxc], B[maxn], dp[maxc][maxn];
  7. int main(){
  8.     int n, m;
  9.     scanf("%d %d", &n, &m);
  10.     for(int i = 1; i <= m; i++){
  11.         scanf("%d",&A[i]);
  12.     }
  13.     int L;
  14.     scanf("%d", &L);
  15.     for(int i = 1; i <= L; i++){
  16.         scanf("%d", &B[i]);
  17.     }
  18.     for(int i = 0; i <= m; i++) dp[i][0] = 0;
  19.     for(int i = 0; i <= L; i++) dp[0][j] = 0;
  20.     for(int i = 1; i <= m; i++){
  21.         for(int j = 1; j < L; j++){
  22.             int MAX = max(dp[i][j - 1], dp[i - 1][j]);
  23.             if(A[i] == A[j]) dp[i][j] = MAX + 1;
  24.             else dp[i][j] = MAX;
  25.         }
  26.     }
  27.     printf("%d", dp[m][L]);
  28.     return 0;
  29. }