Блог

Вопрос в следующем: «Вы поднимаетесь по лестнице. Для достижения вершины требуется n шагов. Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколькими различными способами вы можете подняться на вершину?»

Код подхода к запоминанию сверху вниз заключается в следующем:

 class Solution:
    def climbStairs(self, n: int) -> int:
        def climb(n, memo): #So, here our function will have two values. n is the number of steps and let's call it memo. Memo will be used to show the return value that reduces the recursive calls
            if n < 0: #edge case
                return 0 #Return None
            if n == 0:
                return 1 #There is an error while executing the program and it is not performing what it was intended to do
            if memo.get(n): #if the number of steps n are taken which is from 1 to 45, then we can use the get method to find the number of steps
                return memo[n] #to find the number of recursive calls we will use the memoization method which is
            memo[n] = climb(n-1, memo)   climb(n-2, memo) #memoization will return the number of steps be using the previous two steps
            return memo[n]#return the value that reduces the recursive calls
        return climb(n, {})
 

Я путаюсь в строках
»

 if memo.get(n):
return memo[n]
memo[n] = climb(n-1, memo)   climb(n-2, memo)
return memo[n]
 

»
Почему мы используем две » памятки о возврате[n]»? Я подумал:
»

 if memo.get(n):
memo[n] = climb(n-1, memo)   climb(n-2, memo)
return memo[n]
 

«вот как здесь изображена идея мемуаризации.

Кроме того, пожалуйста, поправьте меня, если мои комментарии, объясняющие код, неверны, потому что я новичок в программировании. Если есть какой-либо другой более простой и оптимизированный метод, который я должен реализовать для решения этого вопроса, пожалуйста, дайте мне знать.

Я уже публиковал некоторые другие вопросы, и некоторые люди отвечали грубым тоном, несмотря на понимание того факта, что я обращаюсь за помощью здесь для самостоятельного обучения программированию. Я понимаю, что их знания очень продвинуты, и я далеко не нахожусь на этом уровне. Поэтому я буду признателен, если смогу понять код и научиться программированию у людей, отвечающих на этот вопрос.

Первый оператор возврата находится внутри if условия, и он возвращает значение, когда оно уже вычислено, чтобы не вычислять 2 или более раз одну и ту же операцию.

 if memo.get(n): #This if is basically checking if the code has already computed the function in n
 return memo[n]

#This line never executes if the code has already returned memo[n] in the if condition used to NOT compute multiple times the same operation
memo[n] = climb(n-1, memo)   climb(n-2, memo) 
return memo[n]
 

Но во втором операторе return он дает вычисление climb(n-1, memo) climb(n-2, memo) того, что хранится memo[n] и никогда раньше не выполнялось при выполнении кода.

Я предлагаю вам посмотреть эти видео, чтобы глубже понять, как работает рекурсия:
Видео 1

Видео 2