动态规划求解二维网格最大代价路径时路径输出异常原因排查

• 核心错误：可变对象引用导致缓存污染
  Python中列表是可变对象，你的代码直接对up['path']/left['path']执行append操作，同时直接修改up['total']/left['total']的值，而up/left都是已经存入memo或者后续会被其他逻辑复用的对象，这会直接把缓存里的原始值改掉，后续其他逻辑复用缓存时拿到的就是被修改过的错误值，这也是你路径里出现(1,1)之后又出现(2,0)这种非法移动、总得分计算错误的根本原因。
• 语法错误：修改后代码最后一个else块里的return left缩进异常，实际运行会直接报语法错误。
• 边界逻辑不严谨：q<0或p<0时返回None，结合缓存污染问题会进一步放大计算错误。

核心调整规则：每次计算当前点的结果时，不要修改上游返回的对象，而是创建全新的对象存入memo，避免污染缓存。

修正后代码如下：

def findMaxPerson1(q, p, grid, memo={}):
    key = f"{q},{p}"
    if key in memo:
        return memo[key]
    if q == 0 and p == 0:
        return {
            'total': grid[q][p],
            'path': [(q, p)]
        }
    if q < 0 or p < 0:
        # 边界返回负无穷，简化后续比较逻辑
        return {'total': float('-inf'), 'path': []}
    up = findMaxPerson1(q-1, p, grid, memo)  # 从上方来
    left = findMaxPerson1(q, p-1, grid, memo)  # 从左方来
    
    if up['total'] >= left['total']:
        current_total = up['total'] + grid[q][p]
        # 新建路径列表，不修改上游的原始path
        current_path = up['path'] + [(q, p)]
    else:
        current_total = left['total'] + grid[q][p]
        current_path = left['path'] + [(q, p)]
    
    # 新建独立对象存入memo，不会影响上游缓存
    res = {'total': current_total, 'path': current_path}
    memo[key] = res
    return res

grid = [
    [1, 2],
    [3, 4],
    [5, 6],
]
print(findMaxPerson1(2, 1, grid, {}))

运行后输出为：{'total': 15, 'path': [(0, 0), (1, 0), (2, 0), (2, 1)]}，符合移动规则和得分计算要求。

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