面试题库 › 算法 / 大模型 › 最长回文子序列(动态规划)

最长回文子序列(动态规划)

难度 ★★★在 3 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

腾讯1猿辅导1华为1

常见岗位:机器学习算法(泛)、C++ / Qt 客户端、C/C++ 软件开发

答案要点

  1. 状态:dp[i][j] 为 s[i..j] 的最长回文子序列长度
  2. 相等时:dp[i][j] = dp[i+1][j-1] + 2
  3. 不等时:dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  4. 边界:dp[i][i] = 1,空区间为 0;按区间长度从小到大或 i 从后往前遍历
  5. 答案 dp[0][n-1],时间和空间 O(n²),可滚动优化到 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题