Grid DP 噩梦：如何每次都精准处理基础情况

发布: 16小时前 (2025年12月14日 GMT+8 04:26)

7 min read

原文: Dev.to

Source: Dev.to

TL;DR

主题： 为基于网格的 DP（路径、障碍物、最小费用）设定基准情况。
面试价值： 展示你理解递推前提条件，而不仅仅是公式本身。
核心步骤： 选择表格方向、初始化首行/首列、处理障碍物、应用递推式。
常见陷阱： 障碍后忘记置零、i/j 索引对齐错误、忽视记忆化默认值。
你将获得： 可视化模板、TypeScript 代码、常见错误以及练习题目。

初学者友好解释

为什么基准情况决定一切

递推只有在相邻单元有效时才成立。若首行或首列的值错误，后续所有单元都会继承错误。把基准情况当作合同的设定。

选取表格方向

决定 dp[i][j] 表示左上角起第 i 行、第 j 列。坚持一种约定，并在编码前重新声明——这在面试沟通指南中被反复强调。

障碍物会改变种子

一旦首行或首列的某个单元被阻塞，该行/列其后所有单元必须为 0。这是大多数教程忽略的陷阱。

步骤式学习指南

1) 定义状态与递推式

对于 带障碍物的唯一路径：dp[i][j] = 到达 (i, j) 的路径数。

递推式：

dp[i][j] = dp[i‑1][j] + dp[i][j‑1]   if grid[i][j] is free

2) 初始化起始单元

如果 grid[0][0] 被阻塞，答案为 0。否则设 dp[0][0] = 1。大声说出来以巩固基准。

3) 种下首行和首列

遍历 j 从 1 … m‑1 处理首行：若该单元开放且前一个单元为 1，则设为 1；否则设为 0。首列同理，遍历 i。在表格中可视化此过程。

4) 填充其余表格

从 (1,1) 开始，对每个单元，如果被阻塞则设 0，否则取上方与左方之和。保持解说简洁。

5) 用小网格验证

测试 2×2、3×3，在 (0,1) 或 (1,0) 放置障碍。绘制表格确保种子在障碍后正确归零。

可视化示例：带障碍物的唯一路径

function uniquePathsWithObstacles(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => Array(cols).fill(0));

  // Start cell
  if (grid[0][0] === 1) return 0;
  dp[0][0] = 1;

  // First row
  for (let j = 1; j < cols; j++) {
    dp[0][j] = grid[0][j] === 0 && dp[0][j - 1] === 1 ? 1 : 0;
  }

  // First column
  for (let i = 1; i < rows; i++) {
    dp[i][0] = grid[i][0] === 0 && dp[i - 1][0] === 1 ? 1 : 0;
  }

  // Rest of the table
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (grid[i][j] === 0) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[rows - 1][cols - 1];
}

注意：一旦首行/首列出现障碍，传播就会停止；所有后续单元保持 0。

实战准备策略

手绘表格

在纸上画 4×4 网格并随意放置障碍。手动填充比仅靠代码更能巩固种子规则。

替换方向

先用行主序填充，再尝试列主序。解释选择的原因在面试中会加分，并且与AI 备考指南相呼应。

添加最小费用变体

将求和改为 min(top, left) + cost[i][j]。种子逻辑保持不变，帮助你认识基准情况跨问题的通用性。

寻求轻度指导

像 LeetCopilot 这样的工具可以在你忽略首行/首列障碍时给出提示，避免在错误递推上浪费时间。

常见错误须避免

忘记起始单元可能被阻塞——始终检查 grid[0][0]，必要时提前返回 0。
障碍后仍继续填 1——一旦在首行/首列遇到阻塞，后面的所有单元都应保持 0。
索引混用——确保 dp[i][j] 始终表示 第 i 行，第 j 列。
默认全为 1——用全 0 初始化 dp，并有目的地种下基准，否则障碍无法正确归零。

FAQ

如何判断基准情况是否正确？

在种子完成后检查首行/首列；它们必须准确反映障碍的分布，然后再填充其余部分。

在练习网格 DP 前应该做哪些准备？

熟悉二维数组的操作以及更简单的 1 维 DP（如爬楼梯）会帮助你快速上手。

网格 DP 在面试中重要吗？

非常重要——它常出现于路径、费用和计数类题目，面试官经常通过基准情况来检验你的思考深度。

能否改用一维滚动数组？

可以，但前提是基准情况已经正确实现；首行/首列的逻辑仍然必须保留。

结论

在网格 DP 中把基准情况做好，能够防止错误级联，并向面试官展示你从第一原则出发的思考方式。仔细种下起始单元、在障碍后归零，递推式自然会给出正确答案。