使用最小花费爬楼梯(LC746)
哪些公司问过
答案要点
- dp[i] 为到达第 i 阶的最小花费,dp[0] = dp[1] = 0
- 转移:dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
- 等价定义:dp[i] = cost[i] + min(dp[i-1], dp[i-2]),答案取 min(dp[n-1], dp[n-2])
- 只依赖前两项,滚动变量把空间降到 O(1)
易错点
- 把楼顶当成最后一个台阶,答案下标差一
- 两种 dp 定义混用导致初始化错误
- 没先确认费用是踩上去付还是离开时付
面试官常见追问
- 如果每次可以爬 1 到 k 阶呢?
- 如果要输出具体走法怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场