最短路径(给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。用Java代码怎么实现
时间: 2024-01-21 21:15:50 浏览: 27
可以使用动态规划来解决这个问题。假设我们有一个 $m \times n$ 的矩阵 $grid$,其中 $grid_{i,j}$ 表示从左上角到达 $(i,j)$ 点的最小路径和。那么我们可以得到以下递推式:
$$grid_{i,j} = \min(grid_{i-1,j}, grid_{i,j-1}) + grid_{i,j}$$
其中 $i > 0$ 且 $j > 0$,因为第一行和第一列只能由一个方向到达。最后返回 $grid_{m-1,n-1}$ 即可。
Java代码实现如下:
```java
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 初始化第一行和第一列
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i-1][0];
}
for (int j = 1; j < n; j++) {
grid[0][j] += grid[0][j-1];
}
// 递推计算最小路径和
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
```