当然！下面是关于 动态规划（DP）——路径问题 的详细讲解，涵盖经典模型、思路解析及代码示例。

动态规划 —— 路径问题全解

目录

  1. 动态规划简介
  2. 路径问题的动态规划模型
  3. 经典路径问题类型
  4. 核心状态设计与状态转移方程
  5. 代码示例
  6. 常见变形与优化技巧
  7. 经典题目推荐
  8. 总结

1️⃣ 动态规划简介

动态规划是一种通过将复杂问题分解成子问题，记录子问题的结果以避免重复计算的优化方法。适用于具有“重叠子问题”和“最优子结构”性质的问题。

2️⃣ 路径问题的动态规划模型

路径问题通常在二维网格或图中寻找满足某种条件的路径，如：

  • 最短路径
  • 最大/最小路径和
  • 路径计数
  • 满足约束的路径数目

常见场景：二维矩阵中从起点到终点的路径求解。

3️⃣ 经典路径问题类型

类型说明示例题目
最短路径和找到路径和最小的路径LeetCode 64 最小路径和
路径计数计算有多少条路径达到终点LeetCode 62 不同路径
带障碍物路径计数计算无障碍路径数量LeetCode 63 不同路径 II
最大路径和路径和最大LeetCode 120 三角形最小路径
带约束路径路径满足特定条件复杂路径规划问题

4️⃣ 核心状态设计与状态转移方程

假设网格大小为 m x n，起点为 (0,0)，终点为 (m-1,n-1)。

  • 状态定义：dp[i][j] 表示到达位置 (i,j) 的某种最优值（路径和、路径数等）。
  • 转移方程：根据问题不同，转移公式会有差异。
    常见转移为：

dp[i][j]=f(dp[i−1][j],dp[i][j−1])

其中 f 是某种操作，比如求和、取最小、取最大等。

5️⃣ 代码示例

5.1 最小路径和（LeetCode 64）

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]

    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

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

5.2 不同路径数（LeetCode 62）

def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]  # 第一行和第一列均为1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

5.3 带障碍物的不同路径数（LeetCode 63）

def unique_paths_with_obstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0

    for i in range(1, m):
        dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0

    for j in range(1, n):
        dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0

    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            else:
                dp[i][j] = 0

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

6️⃣ 常见变形与优化技巧

  • 空间优化：二维 dp 数组可压缩为一维，节省空间。
  • 路径恢复：记录选择方向，输出路径。
  • 多种移动方式：除上下左右，还可斜向移动。
  • 复杂约束：如必须经过特定点、路径代价限制等，状态设计要更细化。

7️⃣ 经典题目推荐

题号题目名称题型简述
62不同路径计数路径数
63不同路径 II带障碍物的路径计数
64最小路径和路径代价最小
120三角形最小路径和非矩形网格路径求最小和
931下降路径最小和限制方向移动的最小路径和

8️⃣ 总结

路径问题是动态规划的经典应用场景。核心在于：

  • 明确状态含义
  • 准确设计状态转移
  • 注意边界初始化
  • 结合具体问题灵活调整

掌握路径DP，有助于解决大量实际与竞赛中的复杂路径规划问题。

如果需要，我可以帮你写更复杂的路径问题解析，或者路径恢复代码，随时告诉我！