最长公共子序列

AC代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
      int dp[1005][1005] = {0};
      int n = text1.size();
      int m = text2.size();
      for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++){
              if (text1[i-1] == text2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
              else{
                  dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
              }
          }
      }
      return dp[n][m];
  }
};

1.max里面为何只有两种情况，为何不需要比较dp[i-1][j-1]的情况？

原因：dp[i][j-1]的值与dp[i-1][j]的值都一定大于等于dp[i-1][j-1]所以无需判断。

2.编写代码输出 最长公共子序列的长度、其中一个最长公共子序列。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

string text1, text2;
int dp[1005][1005] = {0};

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size();
    int m = text2.size();
    // 不再重新定义 dp，直接使用全局 dp 数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1[i-1] == text2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[n][m];
}

void print(int i, int j) {
    if (i == 0 or j == 0) return;
    if (dp[i][j] == dp[i - 1][j - 1] + 1) {
        print(i - 1, j - 1);
        cout << text1[i - 1];
    } else if (dp[i][j] == dp[i - 1][j]) {
        print(i - 1, j);
    } else {
        print(i, j - 1);
    }
}

int main() {
    ios;
    cin >> text1 >> text2;
    int n = text1.size();
    int m = text2.size();
    cout << longestCommonSubsequence(text1, text2) << '\n'; // 输出 LCS 长度
    print(n, m); // 通过递归函数打印 LCS
    cout << '\n';
    return 0;
}

通过递归函数从LCS末尾开始溯源。

当dp[i][j] == dp[i - 1][j - 1] + 1说明上一位置在当前位置的左上角，

当dp[i][j] == dp[i - 1][j]说明上一位置在当前位置的左边，

当dp[i][j] == dp[i][j - 1]说明上一位置在当前位置的上边，