跳到主要内容

网格与路径动态规划

本节目标

以网格位置为状态，统一处理路径计数、路径最优化和局部几何状态。

按行、列推进时，格子通常只依赖上方、左方或下一行相邻位置。关键是先识别答案是路径数量、路径代价还是以当前位置结尾的几何尺寸。

识别信号​

  • 在矩阵中只允许向右、向下移动，询问方案数或最优路径。
  • 三角形从每层只能走到下一层相邻位置。
  • 字符矩阵要求最大的全 1 正方形等局部几何结构。

状态定义与转移推导​

路径计数令 dp[r][c] 为到达格子的路径数，来自上、左之和。最小路径和用上、左的较小累积值加当前格。三角形自底向上令 dp[c] 为下一层可达最大值。最大正方形令 dp[r][c] 为以该格为右下角的最大边长，等于上、左、左上三者最小值加一。

初始化与遍历顺序​

计数的首行首列为 1；路径和分别初始化第一行、第一列累计值。滚动数组从左到右时，dp[c] 仍是上方、dp[c-1] 是左方。三角形必须自底向上，保证两个孩子已就绪；最大正方形额外保存覆盖前的左上角值。

通用模板​

for r in rows:
    for c in cols:
        dp[c] = merge(dp[c], dp[c - 1], grid[r][c])

merge 可是加法、最小值加当前代价，或三邻域最小值加一；状态含义决定初始化。

空间优化与复杂度​

二维网格通常是 O(rc) 时间。若只依赖上一行和当前行左侧，空间可从 O(rc) 压缩为 O(c)；三角形用一行 O(n)。

母题序列​

  1. 不同路径 必学：路径计数。
  2. 最小路径和 必学：最优化路径。
  3. 数字三角形 必学：自底向上选择孩子。
  4. 最大正方形 必学：局部几何状态。

常见误区​

  • 把路径数量与最小代价的初始化混用。
  • 误把 dp[c] 覆盖后当作上方旧状态。
  • 全负三角形用零初始化，意外生成不存在的空路径。
  • 最大正方形只看上和左，遗漏左上角对边长的限制。

迁移方向​

加入障碍物后把不可达路径设为零或无穷大；若可向多方向移动，先重建依赖图，避免沿用单向网格的扫描顺序。