#2070. 最长公共子序列的长度(2023CSP-J程序完善T2)
最长公共子序列的长度(2023CSP-J程序完善T2)
给定两个字符串 x 和 y,求它们的最长公共子序列的长度。
输入格式:
* 第一行:字符串 x。
* 第二行:字符串 y。
输出格式:
* 输出一个整数,表示最长公共子序列的长度。
示例输入:
abcde
ace
示例输出:
3
题思路:
- 使用动态规划算法,创建一个二维数组
dp,其中dp[i][j]表示字符串x的前i个字符和字符串y的前j个字符的最长公共子序列的长度。 - 根据字符匹配情况更新
dp数组。 - 最终
dp[x.size()][y.size()]即为最长公共子序列的长度。