leetcode hot100【LeetCode 64.最小路径和】java实现

LeetCode 64.最小路径和

题目描述

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

每次只能向下或向右移动一步。

示例 1:

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

说明:

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

Java 实现

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // dp 数组用于存储最小路径和
        int[][] dp = new int[m][n];

        // 初始化第一行
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        
        // 初始化第一列
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

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

解题思路

该问题可以使用动态规划（Dynamic Programming, DP）来解决。基本思路是从网格的起点 (0, 0)
出发，计算到达每个位置的最小路径和。我们可以根据到达当前格子的最小路径是从上方还是从左方到达的来更新当前格子的路径和。

1. 定义状态：

   • 设 dp[i][j] 为从起点 (0, 0) 到达位置 (i, j) 的最小路径和。

2. 状态转移：

   • 对于每个格子 (i, j)，可以通过上方 (i-1, j) 或左方 (i, j-1) 来到达，路径的最小值为这两个位置路径和的最小值加上当前格子的值：
     [dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])]
   • 边界条件：如果在第一行或者第一列，机器人只能从左侧或上侧到达，所以路径和应该累加。

3. 边界条件：

   • 第一行和第一列的路径和是累加的，因为机器人只能从左方或上方到达：
     [dp[0][j] = dp[0][j-1] + grid[0][j]]
     [dp[i][0] = dp[i-1][0] + grid[i][0]]

4. 求解： 最终结果为 dp[m-1][n-1]，即到达右下角的最小路径和。

复杂度分析

• 时间复杂度：O(m * n)，需要遍历整个 m x n 网格，计算每个位置的最小路径和。
• 空间复杂度：O(m * n)，用于存储 dp 数组。