CODEWITHSUNDEEP
pythonrecursion
Rik
Rik

Reputation: 477

Different ways to traverse flight of stairs

I am trying to write a code in python for the following: There are n stairs. I want to display the different ways(not the sum total no. of ways) of reaching stair n from stair 1. The catch here is i can skip not more than m stairs at a time. Please help. Note: m and n will be input by user. The following code displays the total no of ways. but not what all the different ways are:

# A program to count the number of ways to reach n'th stair


# Recursive function used by countWays
def countWaysUtil(n,m):
  if n <= 1:
      return n
  res = 0
  i = 1
  while i<=m and i<=n:
      res = res + countWaysUtil(n-i, m)
      i = i + 1
  return res

# Returns number of ways to reach s'th stair    
def countWays(s,m):
  return countWaysUtil(s+1, m)



# Driver program

s,m = 4,2
print "Number of ways =",countWays(s, m)

Upvotes: 3

Views: 453

Answers (1)

tobias_k
tobias_k

Reputation: 82919

This seems to be a sort of generalized Fibonacci sequence, except that instead of f(n) = f(n-1) + f(n-2) you have f(n) = f(n-1) + ... + f(n-m). Your code should work, but the massive recursion will give you very high complexity for larger values of n (on the order of O(m^n) if I'm not mistaken). The key to solving this sort of problem is to memorize the results for lower input values in a list:

def ways_up_stairs(n, m):
    ways = [1] + [None] * n
    for i in range(1, n+1):
        ways[i] = sum(ways[max(0, i-m):i])
    return ways[n]

Some example input and output:

print(ways_up_stairs(4,2)) # 5
print(ways_up_stairs(4,3)) # 7
print(ways_up_stairs(4,4)) # 8

If you want the actual step-sequences, not the sums, you can easily adapt the code accordingly, using nested list comprehensions:

def ways_up_stairs(n, m):
    ways = [[(0,)]] + [None] * n
    for i in range(1, n+1):
        ways[i] = [w + (i,) for ws in ways[max(0, i-m):i] for w in ws]
    return ways[n]

print(ways_up_stairs(4,2))
# [(0, 2, 4), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (0, 1, 2, 3, 4)]

Note that you might have to adapt the code a bit, as it is e.g. not really clear whether "skip up to m steps" means that you can take 1..m or 1..m+1 steps, but if you have the expected result for some input, making those "one-off" adaptations should be easy.

Upvotes: 2

Related Questions