Algorithms for Coding Interviews in Python/

...

/

Solution: Staircase Problem

Solution: Staircase Problem

This review contains a detailed analysis of the different ways to solve the staircase problem.

We'll cover the following...

Solution 1: brute force

Python 3.5
def count_ways(n):
    """
    Calculates the number of ways a stair can be climbed
    :param n: Number of stairs
    :return: Number of ways to climb a stair
    """
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return count_ways(n - 1) + count_ways(n - 2) + count_ways(n - 3)
# Driver code to test the above function
if __name__ == '__main__':
    print("Number of ways: ", count_ways(3))

Explanation

This solution works very similarly to the Fibonacci problem’s recursive solution. In fact, it follows the same pattern. The main idea is that if you have n stairs then you can hop either 1 step, 2 step, 3 step.

  1. If you hop 1 step then you have n−1n-1 remaining stairs
  2. If you hop 2 steps then you have n−2n-2 remaining stairs
  3. If you hop 3 steps then you have n−3
...