I'm practicing replacing recursion with while loops, and I'm stuck on the following problem.
How many ways can you go up a staircase of length n if you can only take the stairs 1 or 2 at a time?
The recursive solution is pretty simple:
def stairs(n):
if n <= 1:
return 1
else:
return stairs(n-2) + stairs(n-1)
I feel like the structure for the iterative program should go something like this:
def stairs_iterative(n):
ways = 0
while n > 1:
# do something
ways +=1
return ways
But I don't know what I need to put in the #do something part. Can someone help me? Pseudocode is fine!
This amounts to the top-down (recursive) approach vs. the bottom-up (iterative) approach for dynamic programming.
Since you know that for input n you need all values of stairs(p) for 0 <= p <= n. You can iteratively compute stairs(p) starting at p = 0 until you reach p = n, as follows:
def stairs(n):
table = [1, 1] # p = 0 and p = 1
for i in range(2, n + 1):
table.append(table[i - 2] + table[i - 1])
return table[n]
A different approach than @univerio is to use a list as stack:
def stairs_it(n):
res = 0
stack = [n]
while len(stack) > 0:
curr = stack[0]
stack.remove(curr)
if curr == 0:
res += 0
elif curr == 1:
res += 1
elif curr == 2:
res += 2
else:
stack.append(curr-1)
stack.append(curr-2)
return res
