当前位置： 面试刷题>> 路径数计算 (经典算法题500道)
### 题目描述补充
给定一个`m x n`的网格，网格中的每个格子要么是空地（用`0`表示），要么是障碍物（用`1`表示）。从左上角（`(0, 0)`）到右下角（`(m-1, n-1)`）存在多少条不同的路径？注意，每次移动只能向右或向下移动一个单位。
### 示例
**输入**:
```
grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
```
**输出**: 2
**解释**: 存在两条路径可以从左上角到达右下角，分别是`(0,0) -> (0,1) -> (0,2)` 和 `(0,0) -> (1,0) -> (2,0) -> (2,2)`。
### PHP 示例代码
```php
function uniquePaths($grid) {
$m = count($grid);
$n = count($grid[0]);
// 初始化dp数组
$dp = array_fill(0, $m, array_fill(0, $n, 0));
// 初始化边界条件
for ($i = 0; $i < $m; $i++) {
$dp[$i][0] = 1;
}
for ($j = 0; $j < $n; $j++) {
$dp[0][$j] = 1;
}
// 动态规划填表
for ($i = 1; $i < $m; $i++) {
for ($j = 1; $j < $n; $j++) {
if ($grid[$i][$j] == 0) {
$dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
}
}
}
return $dp[$m-1][$n-1];
}
// 示例用法
$grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
];
echo uniquePaths($grid); // 输出: 2
```
### Python 示例代码
```python
def uniquePaths(grid):
m, n = len(grid), len(grid[0])
# 初始化dp数组
dp = [[0] * n for _ in range(m)]
# 初始化边界条件
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# 动态规划填表
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# 示例用法
grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
print(uniquePaths(grid)) # 输出: 2
```
### JavaScript 示例代码
```javascript
function uniquePaths(grid) {
const m = grid.length;
const n = grid[0].length;
// 初始化dp数组
const dp = Array.from({length: m}, () => Array(n).fill(0));
// 初始化边界条件
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n; j++) {
dp[0][j] = 1;
}
// 动态规划填表
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (grid[i][j] === 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
// 示例用法
const grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
];
console.log(uniquePaths(grid)); // 输出: 2
```
**码小课网站中有更多相关内容分享给大家学习**，欢迎访问码小课网站获取更多算法和数据结构的深入解析和实战案例。