Considering the classical staircase problem as "Davis has a number of staircases in his house and he likes to climb each staircase 1, 2, or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase."
My approach is to use memoization with recursion as
# 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]
The question that comes to my mind is that, is this solution bottom-up or top-down. My way of approaching it is that since we go all the way down to calculate the upper N values (imagine the recursion tree). I consider this bottom-up. Is this correct?
Recoursion strategies are as a general rule topdown approaches, whether they have memory or not. The underlaying algorithm design is dynamic programming, which traditionally built in a bottom-up fashion.
I noticed that you wrote your code in python, and python is generally not happy about deep recoursion (small amounts are okay, but performance quickly takes a hit and there is a maximum recousion depth of 1000 - unless it was changed since I read that).
If we make a bottom-up dynamic programmin version, we can get rid of this recousion, and we can also recognise that we only need constant amount of space, since we are only really interested in the last 3 values:
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]
Notice how much simpler the logic is, appart from the i is one less than the value, since the positions are starts a 0 instead of the count of 1.