Leetcode – Climbing Stairs in Python

Spread the love

The ‘Climbing Stairs’ problem is one of the fundamental problems on LeetCode. In this article, we will provide a detailed walkthrough on how to solve this problem using Python.

Problem Statement

The ‘Climbing Stairs’ problem (LeetCode problem #70) is described as follows:

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Here are a few examples for better understanding:

  • Input: 2 Output: 2 (As there are two ways to climb to the top. 1. 1 step + 1 step, 2. 2 steps)
  • Input: 3 Output: 3 (As there are three ways to climb to the top. 1. 1 step + 1 step + 1 step, 2. 1 step + 2 steps, 3. 2 steps + 1 step)

Understanding the Problem

This problem can be solved by recognizing it as a classical problem in computer science, known as the Fibonacci number problem. In Fibonacci sequence, each number (after the first two) is the sum of the two preceding ones. If we see the ways to climb stairs, we’ll realize that the number of ways to reach the ith stair is the sum of the number of ways to reach the (i-1)th stair and the (i-2)th stair, because at every step we can either take one step or two steps. This is the same recurrence formula as that of the Fibonacci sequence.

Approach to Solve the Problem

There are a few different ways to solve this problem. The two most common approaches are the recursive method and the dynamic programming method. Here, we’ll focus on the dynamic programming solution as it is more efficient.

Step 1: Import Necessary Libraries

In this problem, we don’t need to import any special libraries, so we can skip this step.

Step 2: Create a Function

We will create a function climbStairs which takes an integer n (number of steps) as its parameter:

def climbStairs(n):

Step 3: Initialize the Array for Dynamic Programming

We create an array dp of size n + 1 to store the number of distinct ways to reach each step:

def climbStairs(n):
    dp = [0 for _ in range(n + 1)]

Step 4: Set Initial Conditions

There’s only one way to reach the first step (if it exists), and two ways to reach the second step (if it exists):

def climbStairs(n):
    dp = [0 for _ in range(n + 1)]
    if n > 0:
        dp[1] = 1
    if n > 1:
        dp[2] = 2

Step 5: Calculate the Number of Distinct Ways for Each Step

For each subsequent step, the number of distinct ways to reach that step is the sum of the number of distinct ways to reach the previous step and the step before the previous step:

def climbStairs(n):
    dp = [0 for _ in range(n + 1)]
    if n > 0:
        dp[1] = 1
    if n > 1:
        dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

Finally, we return the number of distinct ways to reach the nth step:

def climbStairs(n):
    dp = [0 for _ in range(n + 1)]
    if n > 0:
        dp[1] = 1
    if n > 1:
        dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Testing the Solution

Let’s test our function with the sample inputs:

print(climbStairs(2)) # Output: 2
print(climbStairs(3)) # Output: 3

The function works as expected and correctly returns the number of distinct ways to climb to the top of the stairs.

Conclusion

The ‘Climbing Stairs’ problem is a classic dynamic programming problem that shares the same underlying structure as the Fibonacci number problem. It’s an excellent problem for learning and understanding dynamic programming and recursion.

Leave a Reply