路径问题 (Path DP)

核心思想

在网格/棋盘中，从起点走到终点，问有多少种走法或最短路径。

---

1. 不同路径 (Unique Paths)

问题

• m×n 网格，左上到右下，只能向右或向下

解法

// dp[i][j] = 到达 (i,j) 的路径数
function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array.from({ length: m }, () =>
    Array(n).fill(1)
  );

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}

// ✅ 空间优化 - 滚动数组
function uniquePathsOptimized(m: number, n: number): number {
  const dp = Array(n).fill(1);

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }

  return dp[n - 1];
}

图解

     0  1  2  3
  ┌─────────────
0 │ 1  1  1  1
1 │ 1  2  3  4
2 │ 1  3  6  10

---

2. 不同路径 II (带障碍)

问题

• 网格中有障碍物，不能经过

function uniquePathsWithObstacles(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array(n).fill(0);
  dp[0] = grid[0][0] === 0 ? 1 : 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dp[j] = 0;
      } else if (j > 0) {
        dp[j] += dp[j - 1];
      }
    }
  }

  return dp[n - 1];
}

---

3. 最小路径和

问题

• 网格中每格有代价，找到左上到右下的最小代价路径

function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array(n).fill(Infinity);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        dp[j] = grid[i][j];
      } else if (i === 0) {
        dp[j] = dp[j - 1] + grid[i][j];
      } else if (j === 0) {
        dp[j] = dp[j] + grid[i][j];
      } else {
        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }

  return dp[n - 1];
}

---

4. 三角形最小路径和

问题

• 三角形数组，从顶部到底部最小路径和

function minimumTotal(triangle: number[][]): number {
  const n = triangle.length;
  const dp = Array(n + 1).fill(0);

  // 从底部向上
  for (let i = n - 1; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
    }
  }

  return dp[0];
}

图解

        2
       / \
      3   4
     / \ / \
    6   5   7
   / \ / \ /
  10  15  9  11

  从底向上: dp[0] = 2 + min(6,10) = 11

---

5. 地下城游戏

问题

• 骑士在 m×n 网格，要救公主，最少初始生命值？

function calculateMinimumHP(dungeon: number[][]): number {
  const m = dungeon.length, n = dungeon[0].length;
  // dp[i][j] = 从 (i,j) 到终点所需最小生命
  const dp = Array(n + 1).fill(Infinity);
  dp[n - 1] = 1;

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      dp[j] = Math.max(1, Math.min(dp[j], dp[j + 1]) - dungeon[i][j]);
    }
  }

  return dp[0];
}

---

6. 路径计数变体

只能向右/下/左/上

function uniquePathsIII(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  let start = [0, 0], end = [0, 0];
  let empty = 0;

  // 找起点终点和空格数
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 0) empty++;
      if (grid[i][j] === 1) start = [i, j];
      if (grid[i][j] === 2) end = [i, j];
    }
  }

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function dfs(i: number, j: number, remain: number): number {
    if (i === end[0] && j === end[1]) {
      return remain === 0 ? 1 : 0;
    }

    let count = 0;
    grid[i][j] = -1; // 标记已访问

    for (const [dx, dy] of dirs) {
      const x = i + dx, y = j + dy;
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] >= 0) {
        count += dfs(x, y, remain - 1);
      }
    }

    grid[i][j] = 0; // 回溯
    return count;
  }

  return dfs(start[0], start[1], empty);
}

---

7. 路径问题分类总结

一维 vs 二维 DP

网格类型	DP 维度	状态定义	空间优化
单向移动（只能右/下）	1D	dp[j] = 到当前行的最小/最大	✅ 可优化
自由移动（可四方向）	2D	dp[i][j] = 到某点的最优	❌ 通常需要
带障碍物	1D	处理边界条件	✅ 可优化

状态转移模式

只能右/下:
dp[i][j] = dp[i-1][j] + dp[i][j-1]

可以四方向:
dp[i][j] = min(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + grid[i][j]

有权重路径:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + weight[i][j]

---

8. 宝石与石头（路径思维扩展）

问题

• J 中宝石，S 中石头，返回 S 中有多少宝石

function numJewelsInStones(jewels: string, stones: string): number {
  const set = new Set(jewels);
  let count = 0;

  for (const stone of stones) {
    if (set.has(stone)) count++;
  }

  return count;
}

思维扩展

路径问题的核心是"遍历所有可能性，找最优解"。宝石问题本质上是"在 S 中找所有属于 J 的字符"，与路径问题有相通之处。

---

9. 最小路径变体

变体1: 礼物的最大价值

function maxValue(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array(n).fill(0);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        dp[j] = grid[i][j];
      } else if (i === 0) {
        dp[j] = dp[j - 1] + grid[i][j];
      } else if (j === 0) {
        dp[j] = dp[j] + grid[i][j];
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }

  return dp[n - 1];
}

变体2: 穿过迷宫的最少步数

function minStepToReachEnd(grid: number[][], target: number[]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(Infinity));
  dp[0][0] = 0;

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  // BFS
  const queue: [number, number][] = [[0, 0]];

  while (queue.length > 0) {
    const [i, j] = queue.shift()!;

    for (const [dx, dy] of dirs) {
      const x = i + dx, y = j + dy;
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (grid[x][y] === 0 && dp[x][y] === Infinity) {
          dp[x][y] = dp[i][j] + 1;
          queue.push([x, y]);
        }
      }
    }
  }

  return dp[target[0]][target[1]];
}

变体3: 概率最大路径

function maxProbability(
  n: number,
  edges: number[][],
  succProb: number[],
  start: number,
  end: number
): number {
  // 建图 + Dijkstra (概率最大 → 乘积最大)
  const graph: [number, number][][] = Array.from({ length: n }, () => []);

  for (let i = 0; i < edges.length; i++) {
    const [a, b] = edges[i];
    graph[a].push([b, succProb[i]]);
    graph[b].push([a, succProb[i]]);
  }

  const dist = Array(n).fill(0);
  dist[start] = 1;

  // 最大堆
  const pq: [number, number][] = [[-1, start]];

  while (pq.length > 0) {
    const [negProb, u] = pq.shift()!;
    const prob = -negProb;

    if (prob < dist[u]) continue;
    if (u === end) return dist[end];

    for (const [v, p] of graph[u]) {
      const newProb = prob * p;
      if (newProb > dist[v]) {
        dist[v] = newProb;
        pq.push([-newProb, v]);
      }
    }
  }

  return 0;
}

---

10. 路径问题进阶技巧

技巧1: 路径压缩

// 在网格中找可达路径，标记已访问
function markPath(grid: number[][], i: number, j: number): void {
  const m = grid.length, n = grid[0].length;

  function dfs(x: number, y: number): boolean {
    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] === -1) {
      return false;
    }

    if (x === m - 1 && y === n - 1) return true;

    grid[x][y] = -1; // 标记已访问

    return dfs(x + 1, y) || dfs(x, y + 1) ||
           dfs(x - 1, y) || dfs(x, y - 1);
  }

  dfs(i, j);
}

技巧2: 滚动数组优化

// 最小路径和 - 空间 O(min(m, n))
function minPathSumOptimized(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;

  if (m === 0) return 0;

  const dp = Array(n).fill(Infinity);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        dp[j] = grid[i][j];
      } else if (i === 0) {
        dp[j] = dp[j - 1] + grid[i][j];
      } else if (j === 0) {
        dp[j] = dp[j] + grid[i][j]; // dp[j] 还是上一行的值
      } else {
        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }

  return dp[n - 1];
}

技巧3: 原地修改

// 直接修改原数组，不使用额外空间
function uniquePathsInPlace(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === -1) {
        grid[i][j] = 0; // 障碍
      } else if (i === 0 && j === 0) {
        grid[i][j] = 1;
      } else {
        grid[i][j] = (i > 0 ? grid[i - 1][j] : 0) +
                     (j > 0 ? grid[i][j - 1] : 0);
      }
    }
  }

  return grid[m - 1][n - 1];
}

---

经典例题

题目	类型	核心要点
网格中的独特路径	一维DP	组合数学
最小路径和	一维DP	贪心不行，必须DP
三角形最小路径	倒序DP	自底向上
地下城游戏	逆序DP	从终点反推
礼物的最大价值	路径DP	带权重
概率最大路径	Dijkstra	概率乘法

---

参见: **DP算法索引** | **序列问题**