7-004-(LeetCode- 64) 最小路径和

arctic_fox / 2023-05-03 / 原文

1. 题目

读题

https://leetcode.cn/problems/minimum-path-sum/

考查点

这道题的考查点主要是动态规划的思想和技巧。动态规划是一种解决复杂问题的方法，它把一个问题分解成若干个子问题，然后从最简单的子问题开始，逐步求解，最终得到原问题的解。动态规划通常需要找到一个合适的状态表示和状态转移方程，以及一个合理的初始化和边界条件。动态规划可以有效地降低时间复杂度，但可能会增加空间复杂度。动态规划的应用范围很广泛，涉及到很多领域，如数学、计算机科学、工程、经济等。

2. 解法

思路

解答思路是这样的：

我们可以把矩阵看成一个有向图，每个格子是一个节点，每个节点有两条边，一条向右，一条向下，边的权值是对应格子的值。
我们的目标是找到从左上角到右下角的最短路径，也就是权值之和最小的路径。
我们可以用动态规划的方法来解决这个问题，定义一个二维数组dp，dp[i][j]表示从左上角到(i,j)的最短路径和。
我们可以从左上角开始，逐行逐列地计算dp数组的值，根据题目的限制，我们只能从上方或者左方到达当前格子，所以dp[i][j]等于上方和左方的较小值加上当前格子的值，即dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
我们最终返回dp[m-1][n-1]，即右下角的值，就是我们要求的答案。

代码逻辑

首先，我们初始化dp数组，将左上角的值赋给dp[0][0]。
然后，我们初始化第一列和第一行的值，因为它们只能从左边或者上边到达，所以它们的值等于前一个格子的值加上当前格子的值。
接着，我们用一个双重循环来遍历矩阵中除了第一行和第一列之外的其他格子，根据状态转移方程来更新dp数组的值。
最后，我们返回dp[m-1][n-1]作为答案。

具体实现

   public static 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];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (i == 0 && j == 0) {
                    continue;
                }
                if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
                }
            }

        }
        return dp[m - 1][n - 1];
    }