面试题库 › C++ / 后端 › 松鼠跳格子捡松子的动态规划

松鼠跳格子捡松子的动态规划

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

哪些公司问过

字节跳动1

常见岗位:C++ 后端

答案要点

  1. 状态:dp[i] 表示跳到第 i 格并拿走松子后的最小累计数,dp[0] = a[0],其余初始化为无穷大
  2. 转移:dp[i] = min(dp[i-3], dp[i-4], dp[i-5]) + a[i],越界或不可达的前驱跳过
  3. 第 1、2 格从起点不可达;从第 i 格能跳出数组的条件是 i ≥ n-5
  4. 答案取 dp[max(0, n-5)] 到 dp[n-1] 的最小值;时间 O(n),滚动数组可把空间降到 O(1)
  5. 若题目求最多松子,把 min 换成 max、无穷大换成负无穷,结构不变

易错点

面试官常见追问

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

相关面试题