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代码用同样的键却返回错误答案,本质是两者的记忆化逻辑完全不同:
Java代码的记忆化定义:
memo[row][col]存储的是从(row, col)位置出发,到最后一行的最小路径和。这个值是固定的,只和当前位置有关,和到达该位置的路径无关——不管怎么走到(row, col),从这里到终点的最小路径和都是唯一的,所以用(row, col)作为键合理。我的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

