You need to enable JavaScript to run this app. LeetCode最小下降路径和:递归记忆化实现的问题排查
优惠活动
大模型
产品
解决方案
定价
更多

LeetCode最小下降路径和:递归记忆化实现的问题排查

关于LeetCode最小下降路径和问题的记忆化递归疑问

给定n×n整数矩阵matrix,返回任意下降路径的最小和。下降路径从第一行任意元素出发,下一行只能选择正下方、左下方或右下方的元素,即从位置(row, col)可到达(row+1, col-1)、(row+1, col)、(row+1, col+1)。这是一道动态规划问题,计划用递归+记忆化方法解决。


官方Java实现(使用(row, col)作为记忆化键)

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int minFallingSum = Integer.MAX_VALUE;
        Integer memo[][] = new Integer[matrix.length][matrix[0].length];

        // 从第一行每个元素开始进行带记忆化的DFS
        for (int startCol = 0; startCol < matrix.length; startCol++) {
            minFallingSum = Math.min(minFallingSum,
                findMinFallingPathSum(matrix, 0, startCol, memo));
        }
        return minFallingSum;
    }

    public int findMinFallingPathSum(int[][] matrix, int row, int col, Integer[][] memo) {
        // 边界情况:列越界返回极大值
        if (col < 0 || col == matrix.length) {
            return Integer.MAX_VALUE;
        }
        // 到达最后一行,返回当前元素值
        if (row == matrix.length - 1) {
            return matrix[row][col];
        }
        // 已计算过该位置,直接返回记忆值
        if (memo[row][col] != null) {
            return memo[row][col];
        }

        // 计算从当前位置出发,下一步三个方向的最小路径和
        int left = findMinFallingPathSum(matrix, row + 1, col, memo);
        int middle = findMinFallingPathSum(matrix, row + 1, col + 1, memo);
        int right = findMinFallingPathSum(matrix, row + 1, col - 1, memo);

        // 记忆当前位置的最小路径和:三个方向的最小值加上当前元素值
        memo[row][col] = Math.min(left, Math.min(middle, right)) + matrix[row][col];
        return memo[row][col];
    }
}

我的初始Python实现(使用(row, col)作为记忆化键,返回错误答案)

import sys
from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        d = {}
        min_sum = sys.maxsize
        for i in range(len(matrix)):
            min_sum = min(min_sum, self.recur(matrix, 1, i, matrix[0][i], d))
        return min_sum

    def recur(self, matrix: [], row: int, col: int, sum: int, d: {}):
        if row >= len(matrix):
            return sum
        if (row, col) not in d:
            l = []
            l.append(self.recur(matrix, row + 1, col, sum + matrix[row][col], d))
            if col - 1 >= 0:
                l.append(self.recur(matrix, row + 1, col - 1, sum + matrix[row][col-1], d))
            if col + 1 < len(matrix):
                l.append(self.recur(matrix, row + 1, col + 1, sum + matrix[row][col+1], d))
            d[row,col] = min(l)
        return d[row,col]

修改后的Python实现(使用(row, col, sum)作为记忆化键,超时)

import sys
from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        d = {}
        min_sum = sys.maxsize
        for i in range(len(matrix)):
            min_sum = min(min_sum, self.recur(matrix, 1, i, matrix[0][i], d))
        return min_sum

    def recur(self, matrix: [], row: int, col: int, sum: int, d: {}):
        if row >= len(matrix):
            return sum
        if (row, col, sum) not in d:
            l = []
            l.append(self.recur(matrix, row + 1, col, sum + matrix[row][col], d))
            if col - 1 >= 0:
                l.append(self.recur(matrix, row + 1, col - 1, sum + matrix[row][col-1], d))
            if col + 1 < len(matrix):
                l.append(self.recur(matrix, row + 1, col + 1, sum + matrix[row][col+1], d))
            d[row,col,sum] = min(l)
        return d[row,col,sum]

核心疑问与问题原因分析

官方Java代码用(row, col)作为记忆化键可以正确运行,但我的Python代码用同样的键却返回错误答案,本质是两者的记忆化逻辑完全不同:

  1. Java代码的记忆化定义:
    memo[row][col]存储的是从(row, col)位置出发,到最后一行的最小路径和。这个值是固定的,只和当前位置有关,和到达该位置的路径无关——不管怎么走到(row, col),从这里到终点的最小路径和都是唯一的,所以用(row, col)作为键合理。

  2. 我的Python代码的记忆化错误:
    你的recur函数中,d[row, col]存储的是从起点走到(row, col)的当前累计和出发,到终点的总路径和。但不同路径到达(row, col)时,累计的sum值不同,此时d[row, col]只会存储第一次计算的结果,后续以不同sum到达该位置时,直接返回旧值,导致结果错误。

举个例子:从起点A走到(row, col)的累计和是10,后续最小路径和是5,总路径和15;从起点B走到(row, col)的累计和是8,后续最小路径和还是5,总路径和应该是13。但你的代码会把15存在d[row, col]里,第二次调用直接返回15,结果错误。

当你把键改为(row, col, sum)时,虽然解决了正确性问题,但sum的取值范围极大,记忆化缓存命中率极低,几乎退化成暴力递归,因此超时。


正确的Python实现思路

和Java代码保持一致,让记忆化存储从(row, col)出发到终点的最小路径和,不依赖当前累计的sum:

from typing import List

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        memo = [[None]*n for _ in range(n)]
        
        def dfs(row, col):
            # 边界越界,返回极大值
            if col < 0 or col >= n:
                return float('inf')
            # 到达最后一行,返回当前元素值
            if row == n - 1:
                return matrix[row][col]
            # 已记忆,直接返回
            if memo[row][col] is not None:
                return memo[row][col]
            # 计算三个方向的最小路径和
            left = dfs(row+1, col-1)
            middle = dfs(row+1, col)
            right = dfs(row+1, col+1)
            # 记忆当前位置的最小路径和
            memo[row][col] = min(left, middle, right) + matrix[row][col]
            return memo[row][col]
        
        # 遍历第一行所有起点,取最小值
        return min(dfs(0, col) for col in range(n))

这样既保证了正确性,又有极高的缓存命中率,不会超时。

内容的提问来源于stack exchange,提问作者Hemanth Annavarapu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.01 20:02:07