Climbing Stairs - Leetcode Solution

The Climbing Stairs problem on LeetCode (Problem #70) is a classic dynamic programming problem. The problem statement is 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?

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3 Output: 3 Explanation: 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

To solve this problem, we can use dynamic programming. Let's define a sub-problem as follows:

dp[i] = number of distinct ways to reach the i-th step.

We can build up the solution for n steps by solving for smaller sub-problems, starting with the base cases:

dp[0] = 1 (there is one way to climb a staircase with 0 steps - do nothing) dp[1] = 1 (there is one way to climb a staircase with 1 step - climb one step)

For i >= 2, we can observe that to reach the i-th step, we can either climb one step from the (i-1)th step, or we can climb two steps from the (i-2)th step. Therefore, the number of distinct ways to reach the i-th step is equal to the sum of the number of ways to reach the (i-1)th step and the number of ways to reach the (i-2)th step:

dp[i] = dp[i-1] + dp[i-2]

The final solution will be the value of dp[n], i.e., the number of distinct ways to reach the nth step.

Let's implement this in Python:

def climbStairs(n: int) -> int: # define base cases dp = [1, 1]

# build up solution for i steps
for i in range(2, n+1):
    dp.append(dp[i-1] + dp[i-2])

return dp[n]

The time complexity of this algorithm is O(n), since we compute the value of dp[i] once for each i from 2 to n. The space complexity is also O(n), since we store the intermediate values of dp[i] in a list. However, we can see that we only need the last two values of dp[i] to compute dp[i+1], so we can optimize the space usage by using just two variables to store these values instead of a list:

def climbStairs(n: int) -> int: # define base cases prev1, prev2 = 1, 1

# build up solution for i steps
for i in range(2, n+1):
    curr = prev1 + prev2
    prev1, prev2 = prev2, curr

return prev2

This implementation also has a time complexity of O(n) and a space complexity of O(1), since we only need to keep track of the previous two values of dp[i], not all the intermediate values.

1