面试题库 › C++ / 后端 › 矩阵最小路径和(动态规划)

矩阵最小路径和(动态规划)

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

哪些公司问过

字节跳动5腾讯1滴滴1华为1网易互娱1

常见岗位:C/C++ 软件开发、机器学习算法(泛)、推理部署与加速、大模型算法、推荐搜索广告

答案要点

  1. 状态:dp[i][j] 表示走到 (i,j) 的最小路径和
  2. 转移:dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
  3. 初始化:dp[0][0] 为自身,第一行和第一列是累加和
  4. 答案是 dp[m-1][n-1],时间 O(mn)
  5. 空间可用一维数组滚动降到 O(n);输出路径需保留二维表回溯

易错点

面试官常见追问

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

相关面试题