Реализовать динамическое программирование в этом алгоритме?

Question

Мне был предложен алгоритм, который поможет решить следующую проблему:

Возьмите сетку NxN. Начинайте в левом верхнем углу и проходите в нижнем правом углу, только вниз или вправо от каждого узла. Например:

grid = [[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