不同路径

不同路径的状态如何定义？

• 问题: 只能向右或向下移动, 求从左上角到右下角的路径数 (62);
• 阶段: 按行列号划分;
• 状态: dp[row][col] 为到达该格的不同路径数量;
• 转移: 只能从上方或左方进入, dp[row][col] = dp[row-1][col] + dp[row][col-1];
• 初值: 首行与首列都只有一条直线路径, 全填 1;
• 答案: dp[m-1][n-1];
• 复杂度: 时间 O(mn), 空间 O(mn);

const uniquePaths = (m, n) => {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  for (let row = 1; row < m; row++) {
    for (let col = 1; col < n; col++) {
      dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
    }
  }
  return dp[m - 1][n - 1];
};

有障碍物时初值为什么不能整行填 1？

• 问题: 网格中有障碍物, 障碍格不可通行 (63);
• 转移: 障碍格的路径数固定为 0, 其余仍为 dp[row-1][col] + dp[row][col-1];
• 初值: 首行首列从起点出发逐个赋值, 遇到障碍立即 break, 后续格子保持 0;
• 原因: 障碍一旦挡住直线路径, 后面的格子无法从起点到达, 不能简单填 1;

const uniquePathsWithObstacles = (obstacleGrid) => {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  for (let row = 0; row < m; row++) {
    if (obstacleGrid[row][0] === 1) break;
    dp[row][0] = 1;
  }
  for (let col = 0; col < n; col++) {
    if (obstacleGrid[0][col] === 1) break;
    dp[0][col] = 1;
  }
  for (let row = 1; row < m; row++) {
    for (let col = 1; col < n; col++) {
      if (obstacleGrid[row][col] === 1) continue;
      dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
    }
  }
  return dp[m - 1][n - 1];
};

空间如何优化到一维？

• 观察: dp[row][col] 只依赖当前行的左一格和上一行的同一列;
• 做法: 用一维数组 dp[col], 更新前 dp[col] 是上一行的值 (上方), dp[col-1] 已是本行的值 (左方);
• 方程: dp[col] += dp[col - 1], 从左到右遍历;