四方向走 N 步回到原点的方案数
哪些公司问过
答案要点
- N 为奇数时答案为 0
- 直接计数:对上下总步数 2k 求和 C(N,2k)·C(2k,k)·C(N−2k,(N−2k)/2)
- 坐标旋转 u=x+y、v=x−y,分解为两个独立一维游走
- 闭式结果:C(N, N/2) 的平方
- 大 N 取模时预处理阶乘与逆元
易错点
- 忽略 N 为奇数的情况
- 只要求上下相等、左右相等,却没有乘上步序排列的组合数
- 大数计算没有取模或用除法直接取模
面试官常见追问
- 为什么旋转后两个方向是独立的?
- DP 怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场