网格路径问题Grid Path Problem是动态规划的经典应用之一广泛用于解决在网格中寻找路径数量、最短路径或带约束的路径问题。它的核心思想是将问题分解为子问题通过状态转移计算从起点到终点的路径信息适合初学者理解动态规划的状态定义、转移方程和边界处理。以下以经典的网格路径问题为例详细讲解其动态规划解法并提供 C# 实现结合斐波那契数列和回文串问题的思想突出动态规划的通用性。一、网格路径问题的核心思想1. 问题描述网格路径问题通常定义在一个 m × n 的网格中目标是从左上角 (0,0) 移动到右下角 (m-1,n-1)每次只能向右或向下移动。常见变种包括路径数量计算所有可能的路径数。最短路径在带权网格中寻找最小路径和。带障碍网格中某些点不可达计算可行路径数或最短路径。2. 动态规划的核心思想重叠子问题网格中的每个点 (i,j) 都可以从 (i-1,j)上或 (i,j-1)左到达子问题重复出现。最优子结构目标点 (m-1,n-1) 的解可以通过子问题 (i-1,j) 和 (i,j-1) 构建。状态定义定义 dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数量或路径和。状态转移路径数量dp[i][j] dp[i-1][j] dp[i][j-1]从上或左到达。最短路径dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]带权网格。带障碍检查 (i,j) 是否可达若不可达则跳过。边界条件初始化第一行和第一列通常只有一条路径或累加权重。对于带障碍问题障碍点的状态设为 0路径数或无穷大路径和。3. 与斐波那契和回文串的联系斐波那契数列一维 DP状态依赖前两个值网格路径是二维 DP状态依赖上和左两个方向。回文串问题二维 DP如 dp[i][j] 判断回文网格路径同样使用二维数组但状态转移更简单固定方向。通用性动态规划的关键在于定义状态和转移方程网格路径问题展示了如何处理多维依赖和边界条件。二、典型网格路径问题的 C# 实现以下以三种经典网格路径问题为例提供 C# 实现并逐步增加复杂性。1. 网格路径数量Unique Paths问题在一个 m × n 网格中从 (0,0) 到 (m-1,n-1)每次只能向右或向下移动计算总路径数。C# 实现csharppublic class UniquePaths { public int CountPaths(int m, int n) { int[,] dp new int[m, n]; // 初始化第一行和第一列 for (int i 0; i m; i) dp[i, 0] 1; for (int j 0; j n; j) dp[0, j] 1; // 动态规划 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i, j] dp[i - 1, j] dp[i, j - 1]; } } return dp[m - 1, n - 1]; } }分析状态定义dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数。状态转移dp[i][j] dp[i-1][j] dp[i][j-1]。边界条件第一行和第一列只有一条路径dp[i][0] 1dp[0][j] 1。时间复杂度O(mn)空间复杂度O(mn)。空间优化由于 dp[i][j] 只依赖上一行和当前行的值可以使用滚动数组csharppublic int CountPathsOptimized(int m, int n) { int[] dp new int[n]; Array.Fill(dp, 1); // 初始化第一行 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[j] dp[j - 1]; } } return dp[n - 1]; }空间复杂度O(n)使用一维数组存储当前行。2. 最小路径和Minimum Path Sum问题在一个 m × n 的网格中每个格子有非负权重求从 (0,0) 到 (m-1,n-1) 的最小路径和只能向右或向下移动。C# 实现csharppublic class MinimumPathSum { public int MinPathSum(int[][] grid) { int m grid.Length, n grid[0].Length; int[,] dp new int[m, n]; // 初始化起点 dp[0, 0] grid[0][0]; // 初始化第一行和第一列 for (int i 1; i m; i) dp[i, 0] dp[i - 1, 0] grid[i][0]; for (int j 1; j n; j) dp[0, j] dp[0, j - 1] grid[0][j]; // 动态规划 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i, j] Math.Min(dp[i - 1, j], dp[i, j - 1]) grid[i][j]; } } return dp[m - 1, n - 1]; } }分析状态定义dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。状态转移dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。边界条件第一行和第一列累加权重。时间复杂度O(mn)空间复杂度O(mn)。空间优化使用一维数组csharppublic int MinPathSumOptimized(int[][] grid) { int m grid.Length, n grid[0].Length; int[] dp new int[n]; // 初始化第一行 dp[0] grid[0][0]; for (int j 1; j n; j) dp[j] dp[j - 1] grid[0][j]; // 动态规划 for (int i 1; i m; i) { dp[0] grid[i][0]; for (int j 1; j n; j) { dp[j] Math.Min(dp[j], dp[j - 1]) grid[i][j]; } } return dp[n - 1]; }空间复杂度O(n)。3. 带障碍的网格路径Unique Paths with Obstacles问题在一个 m × n 网格中某些格子有障碍标记为 1不可通过求从 (0,0) 到 (m-1,n-1) 的路径数。C# 实现csharppublic class UniquePathsWithObstacles { public int UniquePathsWithObstacles(int[][] obstacleGrid) { int m obstacleGrid.Length, n obstacleGrid[0].Length; int[,] dp new int[m, n]; // 初始化起点 dp[0, 0] obstacleGrid[0][0] 0 ? 1 : 0; // 初始化第一行和第一列 for (int i 1; i m; i) { dp[i, 0] (obstacleGrid[i][0] 0 dp[i - 1, 0] ! 0) ? 1 : 0; } for (int j 1; j n; j) { dp[0, j] (obstacleGrid[0][j] 0 dp[0, j - 1] ! 0) ? 1 : 0; } // 动态规划 for (int i 1; i m; i) { for (int j 1; j n; j) { if (obstacleGrid[i][j] 0) { dp[i, j] dp[i - 1, j] dp[i, j - 1]; } } } return dp[m - 1, n - 1]; } }分析状态定义dp[i][j] 表示从 (0,0) 到 (i,j) 的路径数。状态转移若 (i,j) 无障碍dp[i][j] dp[i-1][j] dp[i][j-1]否则dp[i][j] 0。边界条件起点或路径上有障碍时路径数为 0。时间复杂度O(mn)空间复杂度O(mn).空间优化csharppublic int UniquePathsWithObstaclesOptimized(int[][] obstacleGrid) { int m obstacleGrid.Length, n obstacleGrid[0].Length; int[] dp new int[n]; // 初始化第一行 dp[0] obstacleGrid[0][0] 0 ? 1 : 0; for (int j 1; j n; j) { dp[j] (obstacleGrid[0][j] 0 dp[j - 1] ! 0) ? 1 : 0; } // 动态规划 for (int i 1; i m; i) { dp[0] (obstacleGrid[i][0] 0 dp[0] ! 0) ? 1 : 0; for (int j 1; j n; j) { if (obstacleGrid[i][j] 0) { dp[j] dp[j - 1]; } else { dp[j] 0; } } } return dp[n - 1]; }空间复杂度O(n)。三、测试代码以下是测试所有实现的 C# 程序csharpusing System; class Program { static void Main() { // 测试网格路径数量 var uniquePaths new UniquePaths(); Console.WriteLine($Unique Paths (3x7): {uniquePaths.CountPaths(3, 7)}); // 28 Console.WriteLine($Unique Paths Optimized (3x7): {uniquePaths.CountPathsOptimized(3, 7)}); // 28 // 测试最小路径和 var minPathSum new MinimumPathSum(); int[][] grid new int[][] { new int[] {1, 3, 1}, new int[] {1, 5, 1}, new int[] {4, 2, 1} }; Console.WriteLine($Minimum Path Sum: {minPathSum.MinPathSum(grid)}); // 7 Console.WriteLine($Minimum Path Sum Optimized: {minPathSum.MinPathSumOptimized(grid)}); // 7 // 测试带障碍的网格路径 var uniquePathsWithObstacles new UniquePathsWithObstacles(); int[][] obstacleGrid new int[][] { new int[] {0, 0, 0}, new int[] {0, 1, 0}, new int[] {0, 0, 0} }; Console.WriteLine($Unique Paths with Obstacles: {uniquePathsWithObstacles.UniquePathsWithObstacles(obstacleGrid)}); // 2 Console.WriteLine($Unique Paths with Obstacles Optimized: {uniquePathsWithObstacles.UniquePathsWithObstaclesOptimized(obstacleGrid)}); // 2 } }输出Unique Paths (3x7): 28 Unique Paths Optimized (3x7): 28 Minimum Path Sum: 7 Minimum Path Sum Optimized: 7 Unique Paths with Obstacles: 2 Unique Paths with Obstacles Optimized: 2四、与斐波那契和回文串问题的对比状态定义斐波那契一维 DPdp[i] 依赖前两个状态。回文串二维 DPdp[i][j] 依赖内部子串如 dp[i1][j-1]。网格路径二维 DPdp[i][j] 依赖上和左两个方向结构更直观。状态转移斐波那契dp[i] dp[i-1] dp[i-2]固定依赖。回文串依赖首尾字符和子问题逻辑较复杂。网格路径dp[i][j] dp[i-1][j] dp[i][j-1]路径数或取最小值路径和方向固定。优化空间斐波那契优化到 O(1)网格路径优化到 O(min(m,n))回文串优化到 O(n)。网格路径的空间优化滚动数组与斐波那契类似依赖有限的先前状态。问题扩展网格路径问题可以扩展到带权路径、k 步路径、3D 网格等类似回文串问题扩展到模糊匹配或多字符串匹配。五、优化与扩展空间优化所有网格路径问题均可通过滚动数组将空间复杂度从 O(m*n) 降到 O(min(m,n))。对于特殊场景如 m n可以交换行列进一步优化。数学解法对于无障碍的路径数量问题可用组合数公式 C(mn-2, m-1) 解决时间复杂度 O(min(m,n))csharppublic long CountPathsMath(int m, int n) { long result 1; for (int i 0; i m - 1; i) { result result * (m n - 2 - i) / (i 1); } return result; }变种问题k 步路径限制移动步数需增加状态维度如 dp[i][j][k]。路径还原记录转移方向输出具体路径。多方向移动允许对角线移动修改状态转移方程。实际应用机器人导航规划机器人在网格中的路径。游戏设计计算角色移动的可能性或最优路径。网络优化在网格化网络中寻找最小延迟路径。六、总结网格路径问题是动态规划的经典案例展示了如何通过二维状态数组解决路径相关问题。C# 实现中路径数量、最小路径和和带障碍路径问题分别对应不同约束均可通过滚动数组优化空间。相比斐波那契数列一维 DP和回文串问题复杂二维 DP网格路径问题状态转移更直观适合入门学习。开发者可以从这些问题入手逐步扩展到更复杂的动态规划问题如字符串匹配、背包问题等。
