限定天数与步长到达目标的方案数
哪些公司问过
答案要点
- 状态:dp[i][j] 为前 i 天恰好走 j 步的方案数,dp[0][0] = 1
- 转移:dp[i][j] = Σ dp[i-1][j-k],k 为当天允许的步数,答案为 dp[D][T]
- 步数为连续区间时用前缀和优化,复杂度从 O(D·T·m) 降到 O(D·T)
- 每行只依赖上一行,可滚动数组,空间 O(T)
- 取模时前缀和相减要加模数防负;先确认是恰好到达还是到达即停
易错点
- 初始化错误,比如把 dp[0][j] 都设为 1
- 前缀和下标越界,j-k 小于 0 时未截断
- 取模后相减出现负数未修正
面试官常见追问
- 每天步数为 1 到 m 时有组合公式吗?
- 如果允许某天不走(步数可以为 0)怎么改?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场