拨号键盘上跳对角线 n 次的路径计数
哪些公司问过
答案要点
- 根据键盘布局写出每个键的对角相邻关系
- 状态 dp[k][d]:跳 k 次后停在 d 的路径数,初值 dp[0][0]=1
- 转移:dp[k+1][nd] += dp[k][d],滚动数组空间 O(1)
- 奇偶性剪枝:对角移动保持行加列的奇偶,可先判断是否可达
- n 很大时用矩阵快速幂,结果取模防溢出
易错点
- 邻接关系写错,尤其是 0 所在位置
- 忘记结果取模导致溢出
- 没注意奇偶性,对不可达目标仍做大量计算却不自知
面试官常见追问
- 如果改成国际象棋马的走法(LeetCode 935)呢?
- 矩阵快速幂怎么用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场