Является ли рекурсия с мемоизацией в лестничной задаче снизу вверх?

Question

Рассматривая классическую проблему с лестницей так: «У Дэвиса есть несколько лестниц в его доме, и ему нравится подниматься по каждой лестнице на 1, 2 или 3 ступеньки за раз. Будучи очень преждевременным ребенком, он задается вопросом, сколько существует путей».чтобы достичь вершины лестницы. "

Мой подход состоит в том, чтобы использовать памятку с рекурсией как

# TimeO(N), SpaceO(N), DP Bottom Up + Memoization
def stepPerms(n, memo = {}):

    if n < 3:
        return n
    elif n == 3:
        return 4

    if n in memo:
        return memo[n]
    else:
        memo[n] = stepPerms(n - 1, memo) + stepPerms(n - 2 ,memo) + stepPerms(n - 3 ,memo)
        return memo[n]

Вопрос, который мне приходит в голову, заключается в том, является ли это решение снизу вверх илинизходящий.Мой подход к этому состоит в том, что, поскольку мы проделали весь путь вниз, чтобы вычислить верхние значения N (представьте дерево рекурсии).Я считаю это снизу вверх.Это правильно?

Answer 1

Стратегии рекурсии, как правило, подходят сверху вниз, независимо от того, имеют они память или нет.В основе алгоритма лежит динамическое программирование, которое традиционно строится по принципу «снизу вверх».

Я заметил, что вы написали свой код на python, и python, как правило, недоволен глубокой рекурсией (небольшие объемы - это нормально, нопроизводительность быстро падает, и максимальная глубина восстановления равна 1000 - если только она не была изменена с тех пор, как я ее прочитал).

Если мы сделаем версию динамического программирования снизу вверх, мы сможем избавиться от этого восстановления,и мы также можем признать, что нам нужно только постоянное количество места, так как нас действительно интересуют только последние 3 значения:

def stepPerms(n):
    if n < 1: return n
    memo = [1,2,4]
    if n <= 3: return memo[n-1]

    for i in range(3,n):
        memo[i % 3] = sum(memo)
    return memo[n-1]

Обратите внимание, насколько проще логика, если исходить из i, то на один меньшечем значение, так как позиции начинаются с 0 вместо счетчика 1.

Answer 2

В нисходящем подходе сложный модуль делится на подмодули.Так что это подход сверху вниз.С другой стороны, подход снизу вверх начинается с элементарных модулей, а затем объединяет их дальше.

И подход этого решения снизу вверх будет:

memo{}

for i in range(0,3):
   memo[i]=i
memo[3]=4

for i in range(4,n+1):
  memo[i]=memo[i-1]+memo[i-2]+memo[i-3]