请实现一个函数，计算两个字符串的最长公共子序列长度，并说明其时间与空间复杂度。
考察说明
考察动态规划建模能力与编码实现细节
回答思路
- 定义 dp[i][j] 表示第一个串前 i 个字符与第二个串前 j 个字符的最长公共子序列长度
- 正确推导状态转移：字符相等时 dp[i][j]=dp[i-1][j-1]+1，否则取 dp[i-1][j] 与 dp[i][j-1] 较大值
- 给出边界初始化 dp[0][j]=0 与 dp[i][0]=0
- 实现时注意索引与空串处理，并准确分析 O(n*m) 时间与空间复杂度，能提出滚动数组优化到 O(min(n,m)) 空间
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。