本文共 1547 字，大约阅读时间需要 5 分钟。

要在一个m x n网格中找到从左上角到右下角的最小路径和，每次只能向右或向下移动。这个问题可以通过动态规划来解决。动态规划的方法可以在线性时间内计算出最优路径和，适用于各种网格大小。

步骤解释

代码实现

以下是Java代码实现示例：

public class MinimumPathSum {    public int minPathSum(int[][] grid) {        int m = grid.length;        if (m == 0) return 0;        int n = grid[0].length;        if (n == 0) return 0;                int[][] dp = new int[m][n];        dp[0][0] = grid[0][0];                // 填充第一行        for (int j = 1; j < n; j++) {            dp[0][j] = dp[0][j-1] + grid[0][j];        }                // 填充第一列        for (int i = 1; i < m; i++) {            dp[i][0] = dp[i-1][0] + grid[i][0];        }                // 填充其他位置        for (int i = 1; i < m; i++) {            for (int j = 1; j < n; j++) {                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];            }        }                return dp[m-1][n-1];    }}

示例解释

考虑输入网格：

1 3 11 5 14 2 1

动态规划表格填充过程：

• dp[0][0] = 1
• 第一行：dp[0] = [1, 4, 5]
• 第一列：dp[:,0] = [1, 2, 8]
• 填充其他位置：
  • dp[1][1] = min(2, 4) + 5 = 2 + 5 = 7
  • dp[1][2] = min(7, 5) + 1 = 5 + 1 = 6
  • dp[2][1] = min(8, 7) + 2 = 7 + 2 = 9
  • dp[2][2] = min(9, 6) + 1 = 6 + 1 = 7

最终输出：7，与示例结果一致。

总结

通过动态规划，我们能够有效地找到网格中的最小路径和，该方法在O(mn)的时间复杂度下完成计算，适用于各种大小的网格问题。