python - 在这个算法中实现动态规划？

Question

我得到了一个可以帮助我解决以下问题的算法:

采用NxN 网格。从左上角开始，仅从每个节点向下或向右遍历到右下角。例如:

网格 = [[0,2,5],[1,1,3],[2,1,1]]

将此列表想象成一个网格:

0 2 5
1 1 3
2 1 1

您访问的每个数字都必须添加到运行总数中。在这种情况下，有六种不同的方法可以查明总金额。我得到的算法适用于此并返回可能的总和列表如下:

def gridsums(grid, x, y, memo):
if memo[x][y] is not None:
    return memo[x][y]

if x == 0 and y == 0:
    sums = [0]
elif x == 0:
    sums = gridsums(grid, x, y-1, memo)
elif y == 0:
    sums = gridsums(grid, x-1, y, memo)
else:
    sums = gridsums(grid, x-1, y, memo) + gridsums(grid, x, y-1, memo)

sums = [grid[x][y] + s for s in sums]
memo[x][y] = sums
return sums

def gridsumsfast(grid):
memo = []
for row in grid:
    memo.append([])
    for cell in row:
        memo[-1].append(None)

return gridsums(grid, len(grid[0]) - 1, len(grid) - 1, memo)

缩进不正确，但您明白了。然而，这适用于更大的 N 值，它根本无法正常工作。例如，当 N 值达到 20 时，它会花费很长时间，并且在我运行的某些测试中会超时。

很明显，主函数做了很多重复的工作，那么我究竟该如何用这个算法实现记忆化/动态规划呢？这项工作重复了很多次，这让我有理由说需要实现动态规划，但是以下行:sum = [grid[x][y] = s for s in sums] 让我失望了因为 x 和 y 会随着每个值的变化而变化，所以我只需要将之前的总和提交到备忘录中，但我无法完全理解这样做。

感谢任何正确方向的指导，谢谢。

Answer 1

所有路径都从上方或左侧到达单元格。如果您从左到右、从上到下遍历网格，您可以累加已经计算出的单元格的总和。思路和TravisJ's answer一样.

def gridsums(grid):
    previous_row_sums = [set() for _ in grid[0]]
    previous_row_sums[0].add(0) #seed
    for row in grid:
        left_sums = set()
        row_sums = []
        for value, above_sums in zip(row, previous_row_sums):
            old_sums = left_sums | above_sums
            sums = {value + old for old in old_sums}
            row_sums.append(sums)
            left_sums = sums
        previous_row_sums = row_sums
    return sums