互联网/IT行业面试题更新 2026-08-05
请手写实现最长公共子序列（LCS）算法，并说明其时间复杂度和空间复杂度。
北京智谱华章科技人工智能互联网/IT编码实现问题拆解技术原理
考察说明
考察动态规划基础、LCS递推关系及复杂度分析
回答思路
- 正确实现动态规划二维表或优化空间版本
- 给出递推关系：匹配时取左上方值加1，不匹配时取上方或左方最大值
- 说明时间复杂度和空间复杂度
- 能描述回溯构造LCS序列的方法
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。
