最小路径和

难度:

标签:

题目描述

给定一个包含非负整数的 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

代码结果

运行时间: 72 ms, 内存: 20.1 MB

/**
 * Problem Description:
 * Given a grid of non-negative integers, find a path from the top-left corner to the bottom-right corner,
 * such that the sum of the numbers along the path is minimized. You can only move either down or right at any point.
 */
import java.util.stream.IntStream;
 
public class Solution {
    public int minPathSum(int[][] grid) {
        // Get the dimensions of the grid
        int m = grid.length;
        int n = grid[0].length;
        // Initialize a 1D array to store the minimum path sum up to each cell in the current row
        int[] dp = new int[n];
        // Fill the dp array using Java Streams
        IntStream.range(0, m).forEach(i -> {
            IntStream.range(0, n).forEach(j -> {
                if (i == 0 && j == 0) {
                    // Starting point
                    dp[j] = grid[i][j];
                } else if (i == 0) {
                    // If we're on the first row, we can only come from the left
                    dp[j] = dp[j - 1] + grid[i][j];
                } else if (j == 0) {
                    // If we're on the first column, we can only come from above
                    dp[j] = dp[j] + grid[i][j];
                } else {
                    // Otherwise, take the minimum path sum from either the left or above
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                }
            });
        });
        // The last element contains the minimum path sum to the bottom-right corner
        return dp[n - 1];
    }
}

解释

方法:

该题解使用动态规划的方法，通过递归的方式从左上角到右下角计算最短路径和。使用记忆化搜索避免重复计算已经计算过的子问题。具体思路是：对于网格中的每个位置 (i, j)，最短路径和等于上方 (i-1, j) 和左方 (i, j-1) 两个位置的最短路径和的较小值，再加上当前位置的值 grid[i][j]。通过递归和记忆化，自底向上地计算出整个网格的最短路径和。

时间复杂度:

O(m * n)

空间复杂度:

O(m * n)

代码细节讲解

🦆

为什么选择动态规划作为解决这个问题的方法？这个问题有哪些特征使其适合使用动态规划？

▷

动态规划适用于解决具有重叠子问题和最优子结构特性的问题。在最小路径和问题中，从任一点到达终点的最小路径依赖于它的子问题（即从它的上方和左方位置到达终点的最小路径），这构成了重叠子问题。同时，问题的最优解可以通过合并子问题的最优解得到，这体现了最优子结构特性。因此，动态规划是解决这类问题的一个有效方法。

🦆

在递归函数中，为什么当`i < 0`或`j < 0`时返回`float('inf')`而不是其他值？

▷

在递归函数中返回`float('inf')`是为了正确处理边界外的情况。由于网格的索引从0开始，任何小于0的索引都代表越过了网格的边界。在求解最小路径和时，边界外的路径不是有效路径，因此应当被忽略。返回`float('inf')`意味着这些路径的代价无限大，确保在比较路径长度时，这些无效路径不会被选取。

🦆

递归解法中使用记忆化存储的策略是否有可能导致内存使用过高，尤其是在网格尺寸非常大时？

▷

是的，递归解法中使用记忆化存储的策略可能会导致内存使用过高。这是因为记忆化存储需要为每一个网格单元存储一个计算结果，如果网格的尺寸非常大，这将需要消耗大量的内存空间。在极端情况下，可能导致内存溢出。因此，在处理大规模数据时，可能需要考虑其他更内存效率的方法，例如迭代动态规划。

🦆

这种递归加记忆化的方法与直接使用迭代动态规划表有什么优劣比较？

▷

递归加记忆化的方法通常更容易实现和理解，特别是在逻辑较为复杂的情况下，因为它更接近问题的自然形式。然而，这种方法可能会因为递归深度过深而导致栈溢出。相比之下，迭代动态规划表不涉及递归调用，因此不会有栈溢出的风险，且通常在空间利用上更加灵活和高效，特别是可以通过状态压缩等技术进一步减少内存使用。但迭代方法在理解和代码实现上可能较为复杂。

相关问题

不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10⁹

地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只向右或向下移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

示例 2：

输入：dungeon = [[0]]
输出：1

提示：

m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

示例 1：

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。

示例 2：

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

提示：

n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 为 -1、0 或 1
grid[0][0] != -1
grid[n - 1][n - 1] != -1

不同路径 II 有效数字