为计算矩阵最短路径数的Python递归函数添加记忆化优化

原可运行的递归代码 #

这段代码可以正确计算从矩阵左上角到右下角的最短路径数（仅允许向右或向下移动时，最短路径步数固定，路径数等价于组合数C(n+m-2, n-1)）：

def matrix_explorer(n,m):
    """
    Recursive function that find number of the shortest paths from beginning cell of matrix to last cell
    :param n: Integer, how many rows has matrix
    :param m: Integer, how many columns has matrix
    :return: Number of the shortests paths
    """
    count=0     # Number of paths
    if n == 1 or m == 1:    # Stop condition, if one of cells is equal to 1
        return count+1    # Add to number of paths 1
    else:
        return matrix_explorer(n-1, m) + matrix_explorer(n, m-1)   # Go to cell above or left to current cell

问题代码的错误点 #

你编写的记忆化版本存在两个核心问题：

• 每次调用matrix_explorer_cache都会新建空字典dictionary，之前计算的结果无法被缓存，完全起不到记忆化优化的作用。
• 直接使用dictionary[n][m]会触发KeyError，因为字典中不存在键n时，访问dictionary[n]会报错，嵌套字典的赋值需要先确保外层键存在。

修复后的记忆化实现 #

方式一：手动维护缓存字典（默认参数方式） #

通过默认参数复用同一个缓存字典，用元组(n,m)作为缓存键避免嵌套字典的问题：

def matrix_explorer_cache(n, m, cache=None):
    # 仅在第一次调用时初始化缓存
    if cache is None:
        cache = {}
    # 先检查缓存，存在则直接返回
    if (n, m) in cache:
        return cache[(n, m)]
    # 终止条件
    if n == 1 or m == 1:
        result = 1
    else:
        # 递归计算并缓存结果
        result = matrix_explorer_cache(n-1, m, cache) + matrix_explorer_cache(n, m-1, cache)
    # 将结果存入缓存
    cache[(n, m)] = result
    return result

方式二：使用标准库装饰器（更简洁） #

利用functools.lru_cache自动处理缓存逻辑，代码更简洁易读：

from functools import lru_cache

@lru_cache(maxsize=None)
def matrix_explorer_cache(n, m):
    if n == 1 or m == 1:
        return 1
    else:
        return matrix_explorer_cache(n-1, m) + matrix_explorer_cache(n, m-1)

两种方式都能有效避免重复计算，大幅提升递归效率，当n和m较大时，记忆化后的时间复杂度从O(2^(n+m))降到O(n*m)。

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