面试题库 › C++ / 后端 › 四方向走 N 步回到原点的方案数

四方向走 N 步回到原点的方案数

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

哪些公司问过

阶跃星辰1

答案要点

  1. N 为奇数时答案为 0
  2. 直接计数:对上下总步数 2k 求和 C(N,2k)·C(2k,k)·C(N−2k,(N−2k)/2)
  3. 坐标旋转 u=x+y、v=x−y,分解为两个独立一维游走
  4. 闭式结果:C(N, N/2) 的平方
  5. 大 N 取模时预处理阶乘与逆元

易错点

面试官常见追问

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

相关面试题