QuanticDev

QuanticDev's Engineering and Software Development Resources

Home View on GitHub

Staircase Problem + 3 Variants - Different Ways to Reach the N’th Stair With M Different Steps

In a staircase problem, you try to calculate the different ways to reach the n’th stair where you are allowed to take up to m steps at a time. Say you are given a staircase problem with 5 stairs to climb, and you can take 1 or 2 steps at a time. How would you solve this problem? This and its variants are the focus of this article. It is a great problem to demonstrate the properties of dynamic programming and how to solve problems with it. Due to this, staircase problem and its variants like unique paths problem are commonly used as programming interview questions.

In this article, you will find the solutions to the following questions, as well as their time and space complexities:

Staircase Problems

Table of contents:

Resources

You can find the video version of this article on YouTube: https://www.youtube.com/watch?v=qSE2iKRU4UA

The video has illustrations for all the problems and their solutions. If you want to read the comments or leave a comment, do so under the YouTube video. If you want to contribute to the article, make a pull request on GitHub.

Solution code to examples are available on:

My other articles relevant to staircase problems:

Recursion visualization tool used in the article:

Overview

Video Solutions

If you want video solutions for the below questions, visit the YouTube link in the resources section. The video has a lot more in-depth info on solution techniques along with helpful visuals.

Staircase Problem - Different Ways to Reach the N’th Stair

Question:

Difficulty:

Requirements:

Analysis:

Formula:

To formulate a way to calculate all possible ways to reach a stair, think in reverse. What are the unique paths that lead to n’th stair. It is the sum of unique paths leading to n-1’th stair plus n-2’nd stairs.

This is Fibonacci Sequence!

Tip: Visualize in a regular (forward) manner and trying to figure out a pattern/formula. If that does not work, try to think in reverse (i.e. reverse path in this question).

Calculate solution for n=4:

Solution: Iteration (Fibonacci Sequence)

Code: Iteration (Fibonacci Sequence)

def ways(n):
a, b = 1, 1
for _ in range(n):
    next_b = a + b
    a = b
    b = next_b
    # shorthand: a, b = b, a + b
return b

Solution: Recursion

Code: Recursion

def ways(n):
if n <= 1:  # Recursion needs to stop at some point!
    return 1
return ways(n-1) + ways(n-2)

Recursion Trees:

Below illustration demonstrates how inefficient recursive solution is. Notice the duplicated branches. They are the source of inefficiency. Solution for this is to use memoization.

Recursion Tree

Following is an illustration of how recursion tree is traversed in our ways() function with 5 steps:

Solution: Recursion With Memoization

Code: Recursion With Memoization

def ways(n, knownWays = {}):
if n <= 1:
    return 1
if n not in knownWays:
    knownWays[n] =
          ways(n-1, knownWays) +
          ways(n-2, knownWays)
return knownWays[n]

Here is another animation of the execution of our memorized ways() function with 5 stairs:

Tips

Generalized Fibonacci-like Sequences

Question:

Difficulty:

Formula:

We generate our formula again using reverse thinking. We will start form the top and calculate unique paths leading to top from previous steps.

* ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... + ways(n-m, m)

Solution: Iteration (Fibonacci-like Sequences)

Code: Iteration (Fibonacci-like Sequences)

def ways(n, m):
stairs = [1]  # index = 0
for _ in range(n):
    stairs.append(sum(stairs))
    if len(stairs) > m:
        stairs.pop(0)
return stairs[-1]

Tips

Generalized Fibonacci-like Sequences With Variable Steps

Question:

Difficulty:

Formula:

Once again, we formulate our solution using top-to-bottom approach.

Solution: Iteration (Fibonacci-like Sequences)

Code: Iteration (Fibonacci-like Sequences)

function ways (n, possibleStepsList) {
const stairs = [1]

for (let i = 1; i <= n; i++) {
  stairs[i] = 0
  possibleStepsList.forEach(s => stairs[i] += stairs[i - s] || 0)
  // todo: trim the stairs array to save space
}

return fib.pop()
}

Tips

Alternative Big O Notation Bug