松鼠跳格子捡松子的动态规划
哪些公司问过
答案要点
- 状态:dp[i] 表示跳到第 i 格并拿走松子后的最小累计数,dp[0] = a[0],其余初始化为无穷大
- 转移:dp[i] = min(dp[i-3], dp[i-4], dp[i-5]) + a[i],越界或不可达的前驱跳过
- 第 1、2 格从起点不可达;从第 i 格能跳出数组的条件是 i ≥ n-5
- 答案取 dp[max(0, n-5)] 到 dp[n-1] 的最小值;时间 O(n),滚动数组可把空间降到 O(1)
- 若题目求最多松子,把 min 换成 max、无穷大换成负无穷,结构不变
易错点
- 忘记第 1、2 格不可达,把它们初始化为 0 或 a[i],导致错误转移
- 答案只取 dp[n-1],漏掉从倒数第 2 到第 5 格直接跳出的情况
- 用 0 而不是无穷大初始化不可达状态,min 会被错误拉低
面试官常见追问
- 如果要求恰好停在最后一格而不是跳出去,怎么改?
- 怎么输出具体的跳跃路径?
- 如果每次可跳的步数范围变成 [l, r] 且很大,怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场