LeetCode第64题最小路径和求助：特定测试用例运行失败

你的代码核心问题是递归分支被提前返回截断，导致只探索了部分路径，无法找到真正的最小路径和。

问题分析 #

看你的path函数：

if m != 0:
    return self.path(grid, m - 1, n, total + grid[m-1][n])
if n != 0:
    return self.path(grid, m, n - 1, total + grid[m][n-1])

当m和n都不为0时，执行第一个if里的return会直接结束当前函数，第二个if的分支完全不会执行。比如输入[[1,2],[1,1]]，你的代码只会走右下角→(0,1)→左上角这条路径（总和4），但漏掉了右下角→(1,0)→左上角这条总和为3的路径，自然返回错误结果。

修正递归代码 #

把两个分支的return去掉，让两个方向的路径都能被探索：

from typing import List

class Solution:
    def __init__(self):
        self.res = float("Inf")
    def minPathSum(self, grid: List[List[int]]) -> int:
        self.path(grid, len(grid) - 1, len(grid[0])- 1, grid[len(grid) - 1][len(grid[0]) - 1])
        return self.res
    
    def path(self, grid, m, n, total):
        if m == n == 0:
            self.res = min(self.res, total)
            return
            
        if m != 0:
            # 去掉return，继续执行后续分支
            self.path(grid, m - 1, n, total + grid[m-1][n])
        if n != 0:
            self.path(grid, m, n - 1, total + grid[m][n-1])

这样修改后，输入[[1,2],[1,1]]时，两个方向的路径都会被遍历，最终res会取到最小的3。

更高效的动态规划解法 #

不过递归暴力解法会存在大量重复计算，当网格规模大时会超时。动态规划是更优的解法：

1. 定义dp[i][j]为从左上角到(i,j)的最小路径和
2. 状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])（只能从上方或左方过来）
3. 边界处理：第一行只能从左向右累加，第一列只能从上到下累加

代码实现：

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 创建dp数组，直接在原网格上修改可以节省空间
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]
        # 填充第一列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        # 填充第一行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        # 填充其他位置
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

甚至可以直接在原网格上修改，不需要额外空间：

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

内容的提问来源于stack exchange，提问作者HotSpices