Java算法题-解析 "最小路径和" 算法问题

题目:
给定一个包含非负整数的 m x n
网格,从左上角到右下角的最小路径和是多少?在每个格子只能向下或者向右移动一步。
引言:
"最小路径和" 是一个关于动态规划和路径计算的问题。解决这个问题需要对路径计算和动态规划有一定的理解,同时需要找到一种方法来逐步计算每个位置的最小路径和。通过解答这个问题,我们可以提升对动态规划和路径计算的考虑,同时也能拓展对二维数组问题的解决方案。
算法思路:
使用动态规划可以有效地解决这个问题。具体思路如下:
- 创建一个与网格大小相同的二维数组
dp
,其中dp[i][j]
表示从左上角到达位置(i, j)
的最小路径和。 - 初始化第一行和第一列的路径和,因为在每个格子只能向下或向右移动,所以第一行和第一列的每个位置的路径和只与前一个位置有关。
- 对于其他位置
(i, j)
,可以从上方(i-1, j)
或左方(i, j-1)
移动一步到达。因此,dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])
。 - 最终,
dp[m-1][n-1]
就是从左上角到达右下角的最小路径和。
代码实现:
以下是使用 Java 实现的 "最小路径和" 算法的示例代码:
public class MinimumPathSum {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// Initialize the first row
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
// Initialize the first column
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// Calculate minimum path sum for other positions
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
}
算法分析:
- 时间复杂度:填充二维数组需要遍历每个位置一次,所以时间复杂度为 O(m * n),其中 m 和 n 是网格的维度。
- 空间复杂度:需要一个二维数组来存储最小路径和,所以空间复杂度为 O(m * n)。
示例和测试:
假设给定网格如下:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
根据算法,从左上角到达右下角的最小路径和为 7。
我们可以使用以下代码进行测试:
public class Main {
public static void main(String[] args) {
MinimumPathSum solution = new MinimumPathSum();
int[][] grid = {
{1,3,1},
{1,5,1},
{4,2,1}
};
int minSum = solution.minPathSum(grid);
System.out.println("Minimum path sum: " + minSum);
}
}
总结:
"最小路径和" 算法题要求计算从左上角到达右下角的最小路径和,是一个关于动态规划和路径计算的问题。通过实现这个算法,我们可以提升对动态规划和路径计算的考虑,同时也能拓展对二维数组问题的解决方案。这个问题强调了如何使用动态规划来计算每个位置的最小路径和。