BAT出来，是不是可以在小公司通杀？

今天想跟大家聊聊一个挺有意思的算法问题——网格中的最短路径。

这是个经典的题目，涉及到的算法技术点其实很基础，但却非常实用，几乎所有初学者在刷算法题的时候都会碰到。你可能见过不同的版本，今天我就来聊聊如何用 Java 来解决它，保证既简单又高效。

首先，来了解一下这个问题的背景。假设有一个二维网格，你的任务是从左上角走到右下角，并且每次只能向右或向下走，目标是找到走到终点的最短路径。这是一个经典的 动态规划 问题，也可以用 BFS（广度优先搜索） 来求解。

动态规划法

在网格中，我们可以用一个二维数组 dp[i][j] 来表示从起点 (0, 0) 到位置 (i, j) 的最短路径长度。那么，状态转移公式其实挺简单的：每到一个新位置，我们就选择从上面或者从左边走来的路径中，取最短的那一个，然后加上当前的权重（一般来说就是1）。

代码实现起来很简洁，先来看一下：

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
                // 定义一个dp数组，表示从(0,0)到(i,j)的最短路径
        int[][] dp = new int[m][n];
                // 初始化dp[0][0]，起点处的最短路径就是grid[0][0]
        dp[0][0] = grid[0][0];
                // 初始化第一行的最短路径，只有一条可能的路径，从左往右
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
                // 初始化第一列的最短路径，只有一条可能的路径，从上往下
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
                // 填充其余的dp数组
        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];
    }
}

在这个代码中，我们用两个循环分别初始化了第一行和第一列，因为这些地方的路径只有一种可能（只能从左或者从上）。然后，我们用 Math.min(dp[i-1][j], dp[i][j-1]) 来决定当前位置的最短路径。

BFS法

另外，如果你更倾向于使用广度优先搜索（BFS），也可以考虑这种方法。这种方法的特点是，它会先遍历离起点最近的节点，因此你每遍历到一个点时，它的最短路径一定是最优的。虽然这个算法在某些场景下可能效率略低，但它提供了一个很直观的解法。

BFS 的思路其实很简单，维护一个队列，把起点入队，然后不断取出队头的节点，向它的邻居节点扩展，直到找到目标节点为止。为了确保路径最短，我们可以在遍历过程中记录每个点的距离。

不过我觉得 BFS 主要是应用于有权图的最短路径问题，对于这个题目，使用动态规划更直观、代码也简洁。

空间优化

既然我们已经讨论了动态规划法，不得不提的是空间优化。上面的代码中我们用了一个 m * n 的二维数组，存储所有的最短路径。其实，如果你仔细想一想，你会发现每次计算 dp[i][j] 时，只需要用到 dp[i-1][j] 和 dp[i][j-1] 的值。也就是说，你只需要一维数组来存储当前行的路径信息，上一行的路径可以直接覆盖掉。这么做不仅能节省空间，还能保持代码的简洁。

这就来一个简单的优化版本：

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
                // 用一维数组保存当前行的最短路径
        int[] dp = new int[n];
                dp[0] = grid[0][0];
                for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + grid[0][i];
        }
                for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];  // 更新第一列
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
                return dp[n - 1];  // 返回右下角的最短路径
    }
}

这个版本的代码只用了一个一维数组来存储每一行的最短路径，空间复杂度从 O(m * n) 优化到了 O(n)。这里的 dp[j] 存储的是当前行第 j 列的最短路径值。

小结

说到这里，大家应该对网格中的最短路径问题有了更清晰的了解。这个问题虽然看起来简单，但却可以通过不同的算法思路来解决。无论是动态规划还是 BFS，每种方法都有其特点。在我看来，动态规划法不仅易于理解，而且在实际应用中也比较常见，特别是在处理二维网格问题时。

以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。