LeetCode题练习与总结：最小路径和--64

一、题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

二、解题思路

初始化 dp 数组的左上角元素为 grid 的左上角元素的值，即 dp[0][0] = grid[0][0]。
遍历 grid 的每一行和每一列，对于第一行和第一列，由于只能从左上角来，所以 dp[i][0] = dp[i-1][0] + grid[i][0] 和 dp[0][j] = dp[0][j-1] + grid[0][j]。
对于其他位置，我们可以从左边或者上边来到当前位置，因此 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
遍历完成后，dp 数组的右下角元素即为所求的最小路径和。

三、具体代码

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        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];
        }

        // 填充 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];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

代码首先进行了一些初始化操作，包括检查输入数组是否为空，以及初始化 dp 数组的边界值。这些操作的时间复杂度是 O(1)。
接着，代码通过两层循环遍历了整个 dp 数组。外层循环遍历行，内层循环遍历列。对于每一行和每一列，代码执行了常数时间的操作来计算 dp 数组的值。
因此，总的时间复杂度是 O(m * n)，其中 m 是 grid 的行数，n 是 grid 的列数。这是因为算法需要对每个元素进行一次计算。

2. 空间复杂度

空间复杂度主要由 dp 数组决定，该数组的大小与输入的 grid 相同，即 m x n。
由于没有使用其他额外的空间（除了一些局部变量，它们的空间消耗与输入数组的大小无关），所以空间复杂度是 O(m * n)。

五、总结知识点

动态规划（Dynamic Programming）: 动态规划是一种算法设计技巧，它将一个复杂问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算。在这段代码中，我们使用动态规划来找到从网格的左上角到右下角的最小路径和。通过构建一个 dp 数组，每个 dp[i][j] 表示到达 grid[i][j] 点的最小路径和。
二维数组的使用: 代码中使用了二维数组 dp 来存储从左上角到每个点的最小路径和。这要求对二维数组的索引和更新有深入的理解。
边界条件的处理: 在动态规划中，正确处理边界条件是非常重要的。在这段代码中，首先检查了输入的 grid 是否为空或者维度是否为 0，然后分别初始化了 dp 数组的第一行和第一列，这是因为第一行和第一列的点只能从一个方向到达（第一行只能从左边到达，第一列只能从上面到达）。
嵌套循环: 代码中使用了两层嵌套循环来遍历和填充 dp 数组。外层循环遍历行，内层循环遍历列。这种循环结构是处理二维数据时常见的模式。
最小值的计算: 在填充 dp 数组时，需要计算每个点的最小路径和。这通过 Math.min(dp[i - 1][j], dp[i][j - 1]) 实现，它比较了从上方和左方到达当前点的路径和，并取最小值。
空间复杂度优化: 尽管代码中直接创建了一个与输入网格同样大小的 dp 数组，但实际上可以通过空间复杂度优化技巧，只使用一维数组或者滚动数组来减少空间消耗。这在处理大规模数据时尤其有用。
函数的返回值: 函数的返回值是 dp 数组右下角的元素，即 dp[m - 1][n - 1]，这代表了从左上角到右下角的最小路径和。