当前位置： 面试刷题>> 最小路径和Ⅰ (经典算法题500道)
### 题目描述补充
题目：**最小路径和Ⅰ**
给定一个 `m x n` 的网格 `grid`，网格中的每个单元格都有一个整数。从左上角开始，每次只能向右或向下移动一格，问从左上角移动到右下角的最小路径和是多少？
### 示例
**输入**:
```
grid = [
[1,3,1],
[1,5,1],
[4,2,1]
]
```
**输出**: 7
**解释**:
从左上角到右下角的最小路径和为 1→3→1→1→1 = 7。
### PHP 示例代码
```php
function minPathSum($grid) {
$m = count($grid);
$n = count($grid[0]);
// 初始化第一行和第一列
for ($i = 1; $i < $m; $i++) {
$grid[$i][0] += $grid[$i-1][0];
}
for ($j = 1; $j < $n; $j++) {
$grid[0][$j] += $grid[0][$j-1];
}
// 填充剩余部分
for ($i = 1; $i < $m; $i++) {
for ($j = 1; $j < $n; $j++) {
$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
// 码小课网站中有更多相关内容分享给大家学习
```
以上示例代码展示了如何使用 PHP、Python 和 JavaScript 来解决“最小路径和Ⅰ”问题。