The question is: "You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?"
The code of Top-down memoization approach is:
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, {})
I am confused with the lines "
if memo.get(n):
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]
" Why are we using two 'return memo[n]'? I thought, "
if memo.get(n):
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]
" is how the memoization idea depicts here.
Also, please correct me if my comments explaining the code is wrong, because I am new to programming. If there is any other easier and better optimized method that i should implement to solve this question, then please let me know.
I posted some other questions before, and some people answered in a rude tone despite understanding the fact that I am seeing for help here for self teaching myself programming. I understand that their knowledge is very advanced, and I am nowhere near the level. So, I will appreciate it if I can understand the code and learn programming from the people answering the question.
The first return statement is inside an if condition, and it returns a value when it's already computed, in order to not compute 2 or more times the same operation.
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]
But in the second return statement, it gives the computation of climb(n-1, memo) + climb(n-2, memo) that is stored on memo[n] and has never been done before in the code execution.
I suggest you to watch these videos to understand more deeply how recursion works:
Video 1
Video 2