合作建网站青岛专业网站制作
一、引言
在算法领域中，网格路径问题是一个经典的动态规划应用场景。这类问题通常涉及在一个二维网格中从起点到终点的路径规划，机器人每次只能向右或向下移动一步。本文将深入探讨两种典型的网格路径问题：基础无障碍版本和带障碍物版本，并详细分析它们的动态规划解法。
二、问题一：基础无障碍网格路径
2.1 问题描述:
一个机器人位于 M 行 N 列网格的左上角 (0,0)，每次只能向右或向下移动一步。目标是到达网格右下角 (M-1,N-1)，求所有可能的路径数量。
输入格式:一行，两个整数，分别表示网格的行数M和列数N(0<M,N≤100)
输出格式:一行，一个整数，表示从左上角走到右下角的不同的路径条数
输入样例:2 3
输出样例:3
2.2 动态规划解法:
我们使用二维数组 dp[i][j] 表示从起点 (0,0) 到达位置 (i,j) 的路径数量。
2.3 状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
2.4 边界条件：
-
第一行所有位置：只能从左边向右移动到达
-
第一列所有位置：只能从上边向下移动到达
2.5 C++ 代码实现:
#include <iostream>
using namespace std;const int MAX_SIZE = 101;
int dp[MAX_SIZE][MAX_SIZE];int main() {int M, N;cin >> 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];}}cout << dp[M-1][N-1];return 0;
}
2.6 算法分析
-
时间复杂度：O(M×N)，需要填充整个网格
-
空间复杂度：O(M×N)，使用二维数组存储中间状态
-
关键点：边界条件的处理是解决问题的基石
三、问题二：带障碍物的网格路径
3.1 问题描述
在基础问题基础上增加障碍物，机器人不能通过障碍物位置。给定障碍物坐标，计算从左上角到右下角的路径数量（无法到达时输出0）。
输入格式:
第一行：两个整数 M 和 N，表示网格的行数和列数
第二行：一个整数 K，表示障碍物的数量
接下来 K 行：每行两个整数 X 和 Y，表示障碍物的坐标（行和列均从0开始计数）
输出格式:
一个整数，表示路径数量（若无法到达，输出0）
输入样例:
5 6
5
1 1
1 3
3 2
3 4
4 3
输出样例:
5
3.2 动态规划解法改进
使用二维数组 dp[i][j] 表示到达 (i,j) 的路径数量，obstacle[i][j] 标记障碍物位置。
3.3 状态转移方程：
如果 (i,j) 无障碍物：dp[i][j] = dp[i-1][j] + dp[i][j-1] 否则：dp[i][j] = 0
3.4 边界条件调整：
-
起点有障碍物：直接返回0
-
第一行/列：一旦遇到障碍物，后续位置均不可达
3.5 C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;const int MAX_SIZE = 101;
int dp[MAX_SIZE][MAX_SIZE];
bool obstacle[MAX_SIZE][MAX_SIZE] = {false};int main() {int M, N, K;cin >> M >> N >> K;// 标记障碍物for (int i = 0; i < K; i++) {int x, y;cin >> x >> y;obstacle[x][y] = true;}// 起点处理if (obstacle[0][0]) {cout << 0;return 0;}// 初始化边界dp[0][0] = 1;for (int i = 1; i < M; i++) dp[i][0] = obstacle[i][0] ? 0 : dp[i-1][0];for (int j = 1; j < N; j++) dp[0][j] = obstacle[0][j] ? 0 : dp[0][j-1];// 动态规划填表for (int i = 1; i < M; i++) {for (int j = 1; j < N; j++) {if (obstacle[i][j]) {dp[i][j] = 0;} else {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}}cout << dp[M-1][N-1];return 0;
}
3.6 算法分析
-
时间复杂度：O(M×N)，与基础版本相同
-
空间复杂度：O(M×N)，需要存储障碍物信息和状态数组
-
关键改进：
-
起点障碍物特殊处理
-
边界条件需要检查障碍物
-
动态规划时跳过障碍物位置
-
四、动态规划优化技巧
4.1 空间优化
可以使用滚动数组将空间复杂度优化为 O(N)：
vector<int> dp(N, 0);
dp[0] = 1;
for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (obstacle[i][j]) {dp[j] = 0;} else if (j > 0) {dp[j] += dp[j-1];}}
}
cout << dp[N-1];
4.2 常见变种问题
-
最小路径和：求路径上数字和的最小值
-
存在负权值：使用不同的动态规划策略
-
四方向移动：增加向上和向左移动能力
-
概率问题：计算成功到达的概率