难度: Medium
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200运行时间: 72 ms
内存: 20.1 MB
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
if (i, j) in memo:
return memo[(i, j)]
if i < 0:
return float('inf')
if j < 0:
return float('inf')
if i == 0 and j == 0:
return grid[0][0]
res = min(dp(i-1, j), dp(i, j-1)) + grid[i][j]
memo[(i, j)] = res
return res
return dp(len(grid)-1, len(grid[0])-1)
该题解使用动态规划的方法，通过递归的方式从左上角到右下角计算最短路径和。使用记忆化搜索避免重复计算已经计算过的子问题。具体思路是：对于网格中的每个位置 (i, j)，最短路径和等于上方 (i-1, j) 和左方 (i, j-1) 两个位置的最短路径和的较小值，再加上当前位置的值 grid[i][j]。通过递归和记忆化，自底向上地计算出整个网格的最短路径和。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
# 如果当前位置已经计算过，直接返回记忆化的结果
if (i, j) in memo:
return memo[(i, j)]
# 如果越界，返回无穷大
if i < 0 or j < 0:
return float('inf')
# 如果到达起点，返回起点的值
if i == 0 and j == 0:
return grid[0][0]
# 递归计算上方和左方位置的最短路径和，取较小值，加上当前位置的值
res = min(dp(i-1, j), dp(i, j-1)) + grid[i][j]
# 记忆化当前位置的结果
memo[(i, j)] = res
return res
# 调用递归函数，从终点开始计算
return dp(len(grid)-1, len(grid[0])-1)
动态规划适用于解决具有重叠子问题和最优子结构特性的问题。在最小路径和问题中，从任一点到达终点的最小路径依赖于它的子问题（即从它的上方和左方位置到达终点的最小路径），这构成了重叠子问题。同时，问题的最优解可以通过合并子问题的最优解得到，这体现了最优子结构特性。因此，动态规划是解决这类问题的一个有效方法。
在递归函数中返回`float('inf')`是为了正确处理边界外的情况。由于网格的索引从0开始，任何小于0的索引都代表越过了网格的边界。在求解最小路径和时，边界外的路径不是有效路径，因此应当被忽略。返回`float('inf')`意味着这些路径的代价无限大，确保在比较路径长度时，这些无效路径不会被选取。
是的，递归解法中使用记忆化存储的策略可能会导致内存使用过高。这是因为记忆化存储需要为每一个网格单元存储一个计算结果，如果网格的尺寸非常大，这将需要消耗大量的内存空间。在极端情况下，可能导致内存溢出。因此，在处理大规模数据时，可能需要考虑其他更内存效率的方法，例如迭代动态规划。
递归加记忆化的方法通常更容易实现和理解，特别是在逻辑较为复杂的情况下，因为它更接近问题的自然形式。然而，这种方法可能会因为递归深度过深而导致栈溢出。相比之下，迭代动态规划表不涉及递归调用，因此不会有栈溢出的风险，且通常在空间利用上更加灵活和高效，特别是可以通过状态压缩等技术进一步减少内存使用。但迭代方法在理解和代码实现上可能较为复杂。