#2070. 最长公共子序列的长度(2023CSP-J程序完善T2)

最长公共子序列的长度(2023CSP-J程序完善T2)

给定两个字符串 xy,求它们的最长公共子序列的长度。


输入格式:


* 第一行:字符串 x


* 第二行:字符串 y


输出格式:


* 输出一个整数,表示最长公共子序列的长度。


示例输入:
abcde
ace
示例输出:
3
题思路:

  1. 使用动态规划算法,创建一个二维数组 dp,其中 dp[i][j] 表示字符串 x 的前 i 个字符和字符串 y 的前 j 个字符的最长公共子序列的长度。
  2. 根据字符匹配情况更新 dp 数组。
  3. 最终 dp[x.size()][y.size()] 即为最长公共子序列的长度。