Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: The Staircase Problem

Explore the staircase problem by applying top-down dynamic programming with memoization. Learn how simple recursion leads to exponential time complexity and how memoization reduces it to polynomial time by avoiding repeated subproblems. This lesson helps you grasp core DP concepts like optimal substructure and overlapping subproblems while improving algorithm efficiency.

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, ...