Является ли рекурсия с мемоизацией в задаче «лестница снизу вверх»?
Рассматривая классическую задачу о лестнице: «У Дэвиса в доме несколько лестниц, и ему нравится подниматься по каждой лестнице на 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 (представьте себе дерево рекурсии). Я считаю это снизу вверх. Это правильно?
Ответы 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]
В двоичном дереве алгоритм, подобный вашему примеру, будет рассматриваться как восходящий? Я так не думаю! Прочтите это : quora.com/…
Это все еще не двоичное дерево, сортировка слиянием изображена там как двоичное дерево, пожалуйста, прочитайте эту статью, если у вас есть leetcode, и вы поймете, что я имею в виду, leetcode.com/explore/learn/card/data-structure-tree/17/…,
Сортировка слиянием, очевидно, следует подходу двоичного дерева. Даже полный подход к бинарному дереву.
Стратегии рекурсии, как правило, представляют собой подходы сверху вниз, независимо от того, есть у них память или нет. В основе разработки алгоритма лежит динамическое программирование, которое традиционно строится снизу вверх.
Я заметил, что вы написали свой код на 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.
В двоичном дереве алгоритм, аналогичный моему алгоритму, будет рассматриваться как восходящий, поскольку результат накапливается снизу вверх, я предполагаю, что терминология BT и DP различается?
Определение не так сильно связано с тем, как меняются результаты, как вы думаете. Двоичные деревья в своей основе представляют собой структуру данных «сверху вниз», поскольку они представляют собой структуру данных, построенную вокруг нисходящего метода «разделяй и властвуй», хотя большинство алгоритмов «разделяй и властвуй», которые я помню, разрабатываются на основе свойств «снизу вверх» (поскольку слияние — это основная часть большинства алгоритмов «разделяй и властвуй», и они построены на восходящих свойствах). Смущенный? Это понятно, потому что «снизу вверх» и «сверху вниз» на самом деле речь идет о том, как мысленно разбить проблему, а не о строгих категориях.
В двоичном дереве алгоритм, аналогичный моему алгоритму, будет рассматриваться как восходящий, поскольку результат накапливается снизу вверх, я предполагаю, что терминология BT и DP различается?