爬楼梯(青蛙跳台阶)
哪些公司问过
答案要点
- 状态转移:dp[n] = dp[n-1] + dp[n-2],最后一步走 1 级或 2 级
- 边界:dp[1] = 1,dp[2] = 2,本质是斐波那契数列变形
- 递归会重复计算,加记忆化或自底向上递推,时间 O(n)
- 只依赖前两项,滚动变量把空间降到 O(1)
- 每次可走 1、2、3 步时加上 dp[n-3];大 n 可用矩阵快速幂
易错点
- 边界 dp[2] 写成 1
- 直接递归不做记忆化,超时
- 忘了滚动变量优化空间
- 把方法数与最小步数混淆
面试官常见追问
- 如果每次可以走 1 步、2 步或 3 步呢?
- 递归实现怎么避免重复计算?
- 怎么做到 O(log n)?
- 如果有些台阶不能踩怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场
- 背包界面优化与背包问题6 场