Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: The Staircase Problem

Solution Review: The Staircase Problem

In this lesson, we will review the staircase problem from the coding challenge in last lesson.

We'll cover the following...

Solution 1: Simple recursion

Python 3.5
def staircase(n, m):
  # base case of when there is no stair
  if n == 0:    
    return 1
  ways = 0
  # iterate over number of steps, we can take
  for i in range(1,m+1):  
    # if steps remaining is smaller than the jump step, skip   
    if i <= n:  
      # recursive call with n i units lesser where i is the number of steps taken here            
      ways += staircase(n-i, m) 
  return ways
print(staircase(4,2))

Explanation

The problem is similar to the Fibonacci numbers algorithm. Instead of binary recursion, we have an m-ary recursion here. Which means every recursive makes, at most, m recursive calls.

The algorithm is pretty intuitive as well. At any step, we have the option to take steps of m different lengths, i.e., we can either take 1 step, 2 steps, or so on up to m steps. Each different step will result in a different path. Therefore, we make recursive calls with each number of steps (from 1 to m). We subtract i from n for each call since we have taken i number of steps at this instance (lines 7-11). Our algorithm will conclude when n becomes equal to 0. This would mean we have reached the top of the staircase, and the path we took to get there constitutes one of the many paths, therefore we will return 1 here (lines 3-4). This is our base case. Look at the following visualization for a dry run of this algorithm.

Time complexity

Every time we can make up to m recursive calls. m recursive calls from m recursive calls ...