Implement Dynamic Programming in this algorithm?

Question

I was provided with an algorithm that would help me solve the following problem:

Take an NxN grid. Start at the top left and traverse to the bottom right only going down or right from each node. For example:

grid = [[0,2,5],[1,1,3],[2,1,1]]

Imagine this list as a grid:

0 2 5
1 1 3
2 1 1

Each number you visit you have to add to the running total. In this case there are six different ways to get to the bottom that provide you with a total sum. The algorithm I was given that would work for this and return a list of possible sums is as follows:

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)

Indentation is not correct but you get the idea. This works however for a much larger value of N, it does not work well at all. For example up to a N value of 20, it takes to long and on some tests I ran it times out.

Obviously there is a lot of repeat work being done by the main function so how exactly can I implement memoization/dynamic programming with this algorithm? The work is repeated a lot of times giving me grounds to say dynamic programming needs to be implemented however the line: sum = [grid[x][y] = s for s in sums] trips me up because x and y change for each value so I would only have to commit the previous sums into a memo however I cannot quite wrap my head around doing so.

Any guidance in the right direction is appreciated, thank you.

Answer 1

All paths arrive in a cell either from above or from left. If you loop through the grid left to right and top to bottom, you can accumulate the sums from cells you have computed already. The idea is the same as in 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