当前位置： 面试刷题>> 最小路径和(经典算法150题)
### 题目描述
给定一个`m x n`的网格，网格中的每个单元格都有一个整数。从左上角开始，你只能向右或向下移动到相邻的单元格。你的任务是找到从左上角到右下角的最小路径和。
**示例**：
网格如下：
```
[
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
```
从左上角到右下角的最小路径和为 `7`。
**注意**：
- 你只能向右或向下移动。
- 网格中至少包含一个单元格。
- 网格中的所有值都是非负整数。
### PHP 示例代码
```php
function minPathSum($grid) {
$m = count($grid);
$n = count($grid[0]);
// 初始化第一行和第一列
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($i == 0 && $j > 0) {
$grid[$i][$j] += $grid[$i][$j - 1];
} elseif ($j == 0 && $i > 0) {
$grid[$i][$j] += $grid[$i - 1][$j];
} elseif ($i > 0 && $j > 0) {
$grid[$i][$j] += min($grid[$i - 1][$j], $grid[$i][$j - 1]);
}
}
}
return $grid[$m - 1][$n - 1];
}
// 示例用法
$grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
];
echo minPathSum($grid); // 输出 7
```
### Python 示例代码
```python
def minPathSum(grid):
m, n = len(grid), len(grid[0])
# 初始化第一行和第一列
for i in range(1, m):
grid[i][0] += grid[i-1][0]
for j in range(1, n):
grid[0][j] += grid[0][j-1]
# 动态规划计算最小路径和
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
# 示例用法
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(minPathSum(grid)) # 输出 7
```
### JavaScript 示例代码
```javascript
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
// 初始化第一行和第一列
for (let i = 1; i < m; i++) {
grid[i][0] += grid[i-1][0];
}
for (let j = 1; j < n; j++) {
grid[0][j] += grid[0][j-1];
}
// 动态规划计算最小路径和
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
// 示例用法
const grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
];
console.log(minPathSum(grid)); // 输出 7
```
这些示例代码均采用了动态规划的思想，通过原地修改网格中的值来避免额外的空间复杂度，最终返回从左上角到右下角的最小路径和。