使用DP，递推关系见代码，先使用大空间的dp数组

#include 
     
      #include 
      
       #include 
       
        using namespace std;int max(int a, int b) {
   return a>b?a:b;}int main() {    int N, M, L, tmp;    scanf("%d", &N);        scanf("%d", &M);    if (M < 1) return 0;    vector
        
          MColors(M);        for (int i=0; i
         
           LColors(L);        for (int i=0; i
          
           =0; i--) { int base = i * cols; for (int j=cols - 2; j>=0; j--) { int mc = MColors[j]; int lc = LColors[i]; if (mc == lc) { dp[base + j] = dp[base + j + cols] + 1; } else { dp[base + j] = max(dp[base + j + 1], dp[base + j + cols]); } } } printf("%d\n", dp[0]); return 0;}
          
         
        
       
      
     

因为递推中只使用了当前行和下一行中的数据，题目又不要求给出完整解，因而可以优化空间如下：

#include 
     
      #include 
      
       #include 
       
        using namespace std;int max(int a, int b) {
   return a>b?a:b;}int main() {    int N, M, L, tmp;    scanf("%d", &N);        scanf("%d", &M);    if (M < 1) return 0;    vector
        
          MColors(M);        for (int i=0; i
         
           LColors(L);        for (int i=0; i
          

curr_row(cols, 0); vector

next_row(cols, 0); for (int i = L-1; i >=0; i--) { for (int j = M - 1; j>=0; j--) { if (MColors[j] == LColors[i]) { curr_row[j] = next_row[j] + 1; } else { curr_row[j] = max(next_row[j], curr_row[j + 1]); } } swap(curr_row, next_row); } printf("%d\n", next_row[0]); return 0;}