5 Best Ways to Program to Find How Many Ways We Can Climb Stairs in Python

Rate this post

πŸ’‘ Problem Formulation: Imagine you are facing a staircase with n steps. You can climb the stairs in either 1-step or 2-step increments. The challenge is to write a Python program that calculates how many unique ways you can climb to the top of the staircase. For example, if n is 3, the desired output is 3 ways: (1,1,1), (1,2), and (2,1).

Method 1: Recursive Approach

The Recursive Approach involves defining a function that calls itself to break down the problem into smaller problems. In this context, the function calculates the number of ways to climb n-1 and n-2 stairs and adds them up to find the total for n stairs.

Here’s an example:

def climb_stairs_recursive(n):
    if n <= 2:
        return n
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

print(climb_stairs_recursive(3))

Output: 3

This code snippet defines the function climb_stairs_recursive() which uses simple base cases for when n is 1 or 2, as there is only 1 or 2 ways to climb the stairs respectively. For n > 2, it calls itself with the parameters (n-1) and (n-2) and adds the result, adhering to the Fibonacci sequence logic.

Method 2: Dynamic Programming

Dynamic Programming is an optimization over recursion that stores the results of subproblems to avoid recomputation. Here, we maintain an array that stores the number of ways to reach each step so that it can be re-used for subsequent calculations.

Here’s an example:

def climb_stairs_dp(n):
    ways = [0]*(n+1)
    ways[1] = 1
    ways[2] = 2
    for i in range(3, n + 1):
        ways[i] = ways[i-1] + ways[i-2]
    return ways[n]

print(climb_stairs_dp(3))

Output: 3

The function climb_stairs_dp() creates a list ways to hold the number of ways to climb to each step, starting with known bases of 1 and 2. It then iterates from step 3 to n, filling in the number of ways by adding the ways to climb to the two previous steps, capitalizing on the bottom-up dynamic programming approach.

Method 3: Iterative Approach with Space Optimization

The Iterative Approach with Space Optimization improves upon the Dynamic Programming method by using two variables to hold the previous two results instead of a full list for all steps, thereby reducing space complexity.

Here’s an example:

def climb_stairs_iterative(n):
    a, b = 1, 2
    for _ in range(2, n):
        a, b = b, a + b
    return b if n > 1 else a

print(climb_stairs_iterative(3))

Output: 3

In the climb_stairs_iterative() function, a and b are used to store the last two results. This efficient iteration updates a and b to represent the next step in the sequence until the top is reached, reducing the space needed to O(1).

Method 4: Using Binet’s Fibonacci Formula

Binet’s Fibonacci formula provides a closed-form solution to calculate the nth Fibonacci number directly without iteration or recursion, applying the golden ratio.

Here’s an example:

from math import sqrt

def climb_stairs_binet(n):
    golden_ratio = (1 + sqrt(5)) / 2
    return int((golden_ratio**(n + 1) - (1 - golden_ratio)**(n + 1)) / sqrt(5))

print(climb_stairs_binet(3))

Output: 3

The function climb_stairs_binet() calculates the (n+1)th Fibonacci number using the golden ratio and the square root of 5. The result is rounded to the nearest whole number to find the number of ways to climb the staircase, providing a direct calculation without loops or recursion.

Bonus One-Liner Method 5: Using Python’s functools

Python’s functools module provides a decorator lru_cache() which can memoize the results of function calls, optimizing repeated calls by storing prior results.

Here’s an example:

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs_memo(n):
    return n if n < 3 else climb_stairs_memo(n - 1) + climb_stairs_memo(n - 2)

print(climb_stairs_memo(3))

Output: 3

The one-liner climb_stairs_memo() function utilizes a decorator from Python’s functools to apply memoization, avoiding the overhead of recomputing the number of a ways to climb to a particular step which greatly improves the efficiency of the recursive approach.

Summary/Discussion

  • Method 1: Recursive Approach. Simple to understand and implement. However, it has poor performance due to redundant calculations, with time complexity of O(2^n).
  • Method 2: Dynamic Programming. More efficient than recursion. Utilizes O(n) space and time complexity is O(n).
  • Method 3: Iterative Approach with Space Optimization. Offers the same time complexity as Dynamic Programming, O(n), but reduces the space complexity to O(1) which is a great improvement.
  • Method 4: Using Binet’s Fibonacci Formula. Provides a direct computation of the result. It’s fast and doesn’t require additional space, however, due to floating-point operations, it might not be accurate for very large values of n.
  • Bonus One-Liner Method 5: Using Python’s functools. A clever use of Python’s built-in caching mechanism to ensure high efficiency in recursive calls. It strikes a balance between ease of implementation and performance.