面试题库 › C++ / 后端 › 不同路径(网格路径数)

不同路径(网格路径数)

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

哪些公司问过

字节跳动6华为4百度2微软1米哈游1网易互娱1

常见岗位:C/C++ 软件开发、Java 后端、C++ 后端、人工智能、推理部署与加速

答案要点

  1. 状态:dp[i][j] 表示到达格子 (i, j) 的路径数
  2. 转移:dp[i][j] = dp[i-1][j] + dp[i][j-1]
  3. 边界:第一行和第一列均为 1;答案是 dp[m-1][n-1]
  4. 一维数组滚动优化,空间从 O(m×n) 降到 O(n)
  5. 组合数学:C(m+n-2, m-1),注意计算时的溢出

易错点

面试官常见追问

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

相关面试题