如何用递归替代For循环实现矩阵最长递增路径求解？

问题描述 #

原代码用于求解矩阵中每个元素值均大于前一个元素的最长路径，但现在要求完全禁止使用for循环。当前代码包含3个for循环（其中2个为嵌套循环），请问是否仅用递归即可解决该问题？

原代码如下：

def path(self, matrix):
    res = 1
    
    # 遍历列表中的每个元素以执行函数
    for row in range (len(matrix)):
      for col in range (len(matrix[0])):
        # 传入当前最大值和新位置，取最大值
        res = max(res, self.dfs(matrix, row, col))

    # 返回最大值
    return res

# 路径比较函数（深度优先搜索）
def dfs(self, matrix, row, col):
    # 如果该位置已访问过，返回缓存中的值
    if (row, col) in self.cache:
      return self.cache[(row, col)]

    # 设置默认值为1
    self.cache[(row, col)] = 1

    # 移动当前关注的单元格
    for rowVal, colVal in self.directions:
      newRow = row + rowVal
      newCol = col + colVal

      # 如果指针可移动（未越界）且新位置值更大，则更新缓存值
      if (0 <= newRow < len(matrix)) and (0 <= newCol < len(matrix[0])) and matrix[row][col] < matrix[newRow][newCol]:
        self.cache[(row, col)] = max(self.cache[(row, col)], 1 + self.dfs(matrix, newRow, newCol))

回答 #

完全可以仅用递归实现，只需要把原代码中的两个for循环逻辑都替换成递归即可：

1. 替换遍历所有矩阵元素的嵌套for循环 #

写一个递归函数来遍历矩阵的每个位置，从(0,0)开始按行优先顺序推进：处理当前位置后，先递归处理右侧列；当列到达矩阵末尾时，递归处理下一行的起始列，直到所有位置遍历完成，同时维护全局的最大路径长度。

2. 替换DFS中遍历方向的for循环 #

把对directions列表的遍历改成递归处理：每次处理列表中的第一个方向，处理完后递归处理剩下的方向子列表，直到方向列表为空，以此替代循环遍历所有方向。

修改后的完整代码示例 #

class Solution:
    def __init__(self):
        self.cache = {}
        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.max_path = 1

    def path(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        self.cache.clear()
        self.max_path = 1
        # 启动递归遍历所有矩阵位置
        self.traverse_matrix(matrix, 0, 0)
        return self.max_path

    def traverse_matrix(self, matrix, row, col):
        # 计算当前位置的最长路径，并更新全局最大值
        current_len = self.dfs(matrix, row, col)
        if current_len > self.max_path:
            self.max_path = current_len
        
        # 递归处理下一个位置：先处理右侧列
        if col + 1 < len(matrix[0]):
            self.traverse_matrix(matrix, row, col + 1)
        # 列到末尾后，处理下一行的起始列
        elif row + 1 < len(matrix):
            self.traverse_matrix(matrix, row + 1, 0)

    def dfs(self, matrix, row, col):
        if (row, col) in self.cache:
            return self.cache[(row, col)]
        
        self.cache[(row, col)] = 1
        # 递归处理所有方向
        self.process_directions(matrix, row, col, self.directions)
        return self.cache[(row, col)]

    def process_directions(self, matrix, row, col, directions):
        if not directions:
            return
        # 取出当前要处理的第一个方向
        row_val, col_val = directions[0]
        new_row = row + row_val
        new_col = col + col_val
        
        if 0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0]) and matrix[row][col] < matrix[new_row][new_col]:
            self.cache[(row, col)] = max(self.cache[(row, col)], 1 + self.dfs(matrix, new_row, new_col))
        
        # 递归处理剩下的方向
        self.process_directions(matrix, row, col, directions[1:])

代码说明 #

• traverse_matrix函数：替代原代码中嵌套的for循环，递归遍历矩阵的每一个位置，每到一个位置就计算其最长路径并更新全局最大值。
• process_directions函数：替代DFS中遍历方向的for循环，递归处理每个方向偏移量，直到所有方向都处理完毕。
• 保留缓存机制，避免重复计算，保证算法效率。

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