二级域名站群,伤豆丁文库网站开发,网站优化公司价格如何计算,做搜狗pc网站软件下载一、引言
在算法领域中#xff0c;网格路径问题是一个经典的动态规划应用场景。这类问题通常涉及在一个二维网格中从起点到终点的路径规划#xff0c;机器人每次只能向右或向下移动一步。本文将深入探讨两种典型的网格路径问题#xff1a;基础无障碍版本和带障碍物版本网格路径问题是一个经典的动态规划应用场景。这类问题通常涉及在一个二维网格中从起点到终点的路径规划机器人每次只能向右或向下移动一步。本文将深入探讨两种典型的网格路径问题基础无障碍版本和带障碍物版本并详细分析它们的动态规划解法。
二、问题一基础无障碍网格路径
2.1 问题描述:
一个机器人位于 M 行 N 列网格的左上角 (0,0)每次只能向右或向下移动一步。目标是到达网格右下角 (M-1,N-1)求所有可能的路径数量。
输入格式:一行两个整数分别表示网格的行数M和列数N(0M,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)
vectorint 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 常见变种问题 最小路径和求路径上数字和的最小值 存在负权值使用不同的动态规划策略 四方向移动增加向上和向左移动能力 概率问题计算成功到达的概率
