面试题库 › C++ / 后端 › 爬楼梯(青蛙跳台阶)

爬楼梯(青蛙跳台阶)

难度 ★☆☆在 18 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

百度4字节跳动3京东2蔚来1拼多多1网易1哔哩哔哩1深信服1TP-Link1米哈游1阿里云1影石3601

常见岗位:C/C++ 软件开发、人工智能、AI 应用 / Agent 开发、大模型算法、C++ 后端

答案要点

  1. 状态转移:dp[n] = dp[n-1] + dp[n-2],最后一步走 1 级或 2 级
  2. 边界:dp[1] = 1,dp[2] = 2,本质是斐波那契数列变形
  3. 递归会重复计算,加记忆化或自底向上递推,时间 O(n)
  4. 只依赖前两项,滚动变量把空间降到 O(1)
  5. 每次可走 1、2、3 步时加上 dp[n-3];大 n 可用矩阵快速幂

易错点

面试官常见追问

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

相关面试题