动态规划（8）：路径问题

引言

在算法世界中，路径问题是一类经典且实用的问题，它们广泛应用于网络规划、机器人导航、游戏开发等众多领域。而动态规划作为解决路径问题的强大工具，能够高效地找出最优路径，无论是寻找最短路径、最小代价路径，还是计算可能的路径数量。

本文将从二维网格中的基本路径问题入手，逐步分析"不同路径"、“最小路径和”、"三角形最小路径和"等经典问题，并探讨路径问题的扩展与变形。

二维网格中的路径问题

路径问题的基本特征

二维网格中的路径问题通常具有以下特征：

1. 网格结构：问题通常在一个二维矩阵或网格中进行，每个单元格可能有不同的属性（如权重、障碍物等）。

2. 移动限制：通常限制移动方向，如只能向右或向下移动，或者只能向相邻的单元格移动。

3. 优化目标：寻找满足特定条件的路径，如最短路径、最小代价路径，或者计算满足条件的路径总数。

4. 起点和终点：通常有明确的起点（如左上角）和终点（如右下角）。

路径问题的动态规划解法框架

路径问题非常适合用动态规划来解决，其一般解题框架如下：

1. 状态定义：通常定义dp[i][j]表示从起点到位置(i,j)的某种属性（如路径数量、最小路径和等）。

2. 状态转移方程：根据移动限制，确定dp[i][j]与哪些前置状态有关，并建立转移方程。

3. 边界条件：确定初始状态，如起点的值。

4. 计算顺序：通常按行或按列遍历，确保计算某个状态时，其依赖的状态已经计算完毕。

5. 结果提取：最终结果通常是dp[m-1][n-1]（假设网格大小为m×n）。

常见的移动限制类型

在路径问题中，常见的移动限制包括：

1. 只能向右或向下移动：这是最基本的限制，适用于"不同路径"等问题。

2. 可以向四个方向移动：上、下、左、右，适用于迷宫类问题。

3. 可以向八个方向移动：包括对角线方向，适用于某些特殊问题。

4. 特定规则限制：如只能向相邻的单元格移动，或者有特定的跳跃规则。

下面，我们将通过几个经典问题，详细分析路径问题的动态规划解法。

经典问题：不同路径

问题描述

LeetCode 62. 不同路径：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

问题分析

这是一个典型的路径计数问题，我们需要计算从左上角到右下角的不同路径数量。由于机器人只能向右或向下移动，所以到达某个位置的路径数量等于从上方到达的路径数量加上从左方到达的路径数量。

动态规划解法

1. 状态定义：dp[i][j] 表示从起点 (0,0) 到达位置 (i,j) 的不同路径数量。

2. 状态转移方程：由于只能从上方或左方到达当前位置，所以：

   dp[i][j] = dp[i-1][j] + dp[i][j-1]
   

3. 边界条件：

   • 第一行的所有位置只能从左侧到达，所以 dp[0][j] = 1（j > 0）
   • 第一列的所有位置只能从上方到达，所以 dp[i][0] = 1（i > 0）
   • 起点 dp[0][0] = 1

4. 计算顺序：按行遍历，从左到右。

5. 结果：dp[m-1][n-1] 就是从起点到终点的不同路径数量。

代码实现

def uniquePaths(m, n):# 创建二维数组，初始值为1（因为第一行和第一列只有一种路径）dp = [[1 for _ in range(n)] for _ in range(m)]# 填充dp数组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]

空间优化

由于当前行的状态只依赖于上一行的状态和当前行左侧的状态，我们可以使用一维数组来优化空间复杂度：

def uniquePaths(m, n):# 创建一维数组，初始值为1dp = [1] * n# 更新dp数组for i in range(1, m):for j in range(1, n):dp[j] += dp[j-1]  # dp[j]表示上一行的值，dp[j-1]表示当前行左侧的值return dp[n-1]

数学解法

这个问题还有一个数学解法。从起点到终点，机器人总共需要移动 m-1 步向下和 n-1 步向右，总共 m+n-2 步。问题转化为：在 m+n-2 步中，选择 m-1 步向下（或选择 n-1 步向右），即组合数 C(m+n-2, m-1) 或 C(m+n-2, n-1)。

def uniquePaths(m, n):return math.comb(m+n-2, min(m-1, n-1))

经典问题：最小路径和

问题描述

LeetCode 64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

问题分析

这是一个典型的最短路径问题，我们需要找到一条从左上角到右下角的路径，使得路径上的数字总和最小。由于只能向右或向下移动，所以到达某个位置的最小路径和等于从上方到达的最小路径和与从左方到达的最小路径和中的较小值，再加上当前位置的值。

动态规划解法

1. 状态定义：dp[i][j] 表示从起点 (0,0) 到达位置 (i,j) 的最小路径和。

2. 状态转移方程：

   dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
   

3. 边界条件：

   • 起点：dp[0][0] = grid[0][0]
   • 第一行：dp[0][j] = dp[0][j-1] + grid[0][j]（j > 0）
   • 第一列：dp[i][0] = dp[i-1][0] + grid[i][0]（i > 0）

4. 计算顺序：按行遍历，从左到右。

5. 结果：dp[m-1][n-1] 就是从起点到终点的最小路径和。

代码实现

def minPathSum(grid):if not grid or not grid[0]:return 0m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]dp[0][0] = grid[0][0]# 初始化第一行for j