一、引言

在算法領(lǐng)域中，網(wǎng)格路徑問(wèn)題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃應(yīng)用場(chǎng)景。這類問(wèn)題通常涉及在一個(gè)二維網(wǎng)格中從起點(diǎn)到終點(diǎn)的路徑規(guī)劃，機(jī)器人每次只能向右或向下移動(dòng)一步。本文將深入探討兩種典型的網(wǎng)格路徑問(wèn)題：基礎(chǔ)無(wú)障礙版本和帶障礙物版本，并詳細(xì)分析它們的動(dòng)態(tài)規(guī)劃解法。

二、問(wèn)題一：基礎(chǔ)無(wú)障礙網(wǎng)格路徑

2.1 問(wèn)題描述:

一個(gè)機(jī)器人位于 M 行 N 列網(wǎng)格的左上角 (0,0)，每次只能向右或向下移動(dòng)一步。目標(biāo)是到達(dá)網(wǎng)格右下角 (M-1,N-1)，求所有可能的路徑數(shù)量。

輸入格式:一行，兩個(gè)整數(shù)，分別表示網(wǎng)格的行數(shù)M和列數(shù)N(0<M,N≤100)
輸出格式:一行，一個(gè)整數(shù)，表示從左上角走到右下角的不同的路徑條數(shù)
輸入樣例:2 3
輸出樣例:3

2.2 動(dòng)態(tài)規(guī)劃解法:

我們使用二維數(shù)組?dp[i][j]?表示從起點(diǎn) (0,0) 到達(dá)位置 (i,j) 的路徑數(shù)量。

2.3 狀態(tài)轉(zhuǎn)移方程：

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

2.4 邊界條件：

• 第一行所有位置：只能從左邊向右移動(dòng)到達(dá)

• 第一列所有位置：只能從上邊向下移動(dòng)到達(dá)

2.5 C++ 代碼實(shí)現(xiàn):

#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;// 動(dòng)態(tài)規(guī)劃填表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 算法分析

• 時(shí)間復(fù)雜度：O(M×N)，需要填充整個(gè)網(wǎng)格

• 空間復(fù)雜度：O(M×N)，使用二維數(shù)組存儲(chǔ)中間狀態(tài)

• 關(guān)鍵點(diǎn)：邊界條件的處理是解決問(wèn)題的基石

三、問(wèn)題二：帶障礙物的網(wǎng)格路徑

3.1 問(wèn)題描述

在基礎(chǔ)問(wèn)題基礎(chǔ)上增加障礙物，機(jī)器人不能通過(guò)障礙物位置。給定障礙物坐標(biāo)，計(jì)算從左上角到右下角的路徑數(shù)量（無(wú)法到達(dá)時(shí)輸出0）。

輸入格式:
第一行：兩個(gè)整數(shù) M 和 N，表示網(wǎng)格的行數(shù)和列數(shù)

第二行：一個(gè)整數(shù) K，表示障礙物的數(shù)量

接下來(lái) K 行：每行兩個(gè)整數(shù) X 和 Y，表示障礙物的坐標(biāo)（行和列均從0開(kāi)始計(jì)數(shù)）

輸出格式:
一個(gè)整數(shù)，表示路徑數(shù)量（若無(wú)法到達(dá)，輸出0）

輸入樣例:
5 6
5
1 1
1 3
3 2
3 4
4 3
輸出樣例:
5

3.2 動(dòng)態(tài)規(guī)劃解法改進(jìn)

使用二維數(shù)組?dp[i][j]?表示到達(dá) (i,j) 的路徑數(shù)量，obstacle[i][j]?標(biāo)記障礙物位置。

3.3 狀態(tài)轉(zhuǎn)移方程：

如果 (i,j) 無(wú)障礙物：dp[i][j] = dp[i-1][j] + dp[i][j-1]
否則：dp[i][j] = 0

3.4 邊界條件調(diào)整：

• 起點(diǎn)有障礙物：直接返回0

• 第一行/列：一旦遇到障礙物，后續(xù)位置均不可達(dá)

3.5 C++ 代碼實(shí)現(xiàn)

#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;// 標(biāo)記障礙物for (int i = 0; i < K; i++) {int x, y;cin >> x >> y;obstacle[x][y] = true;}// 起點(diǎn)處理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];// 動(dòng)態(tài)規(guī)劃填表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 算法分析

• 時(shí)間復(fù)雜度：O(M×N)，與基礎(chǔ)版本相同

• 空間復(fù)雜度：O(M×N)，需要存儲(chǔ)障礙物信息和狀態(tài)數(shù)組

• 關(guān)鍵改進(jìn)：

  1. 起點(diǎn)障礙物特殊處理

  2. 邊界條件需要檢查障礙物

  3. 動(dòng)態(tài)規(guī)劃時(shí)跳過(guò)障礙物位置

四、動(dòng)態(tài)規(guī)劃優(yōu)化技巧

4.1 空間優(yōu)化

可以使用滾動(dòng)數(shù)組將空間復(fù)雜度優(yōu)化為 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 常見(jiàn)變種問(wèn)題

1. 最小路徑和：求路徑上數(shù)字和的最小值

2. 存在負(fù)權(quán)值：使用不同的動(dòng)態(tài)規(guī)劃策略

3. 四方向移動(dòng)：增加向上和向左移動(dòng)能力

4. 概率問(wèn)題：計(jì)算成功到達(dá)的概率