面试题库 › 算法 / 大模型 › 限定天数与步长到达目标的方案数

限定天数与步长到达目标的方案数

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

腾讯1

常见岗位:人工智能

答案要点

  1. 状态:dp[i][j] 为前 i 天恰好走 j 步的方案数,dp[0][0] = 1
  2. 转移:dp[i][j] = Σ dp[i-1][j-k],k 为当天允许的步数,答案为 dp[D][T]
  3. 步数为连续区间时用前缀和优化,复杂度从 O(D·T·m) 降到 O(D·T)
  4. 每行只依赖上一行,可滚动数组,空间 O(T)
  5. 取模时前缀和相减要加模数防负;先确认是恰好到达还是到达即停

易错点

面试官常见追问

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

相关面试题