---
###### tags: `Leetcode`
---
# Leetcode 70. Climbing Stairs

[link](https://leetcode.com/problems/climbing-stairs)

---

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

#### Constraints:

- 1 <= n <= 45

---

The climbStairs method takes an integer n as input, which represents the number of stairs to climb. The goal is to determine the number of distinct ways to reach the top of the stairs.

The inner function climb(n) recursively calculates the number of ways to climb n stairs. It uses the following logic:

If n is 1 or 2, there are exactly n ways to climb the stairs. This serves as the base case for the recursion.

For n greater than 2, the number of ways to climb the stairs is equal to the sum of the number of ways to climb n-1 stairs and the number of ways to climb n-2 stairs. This is because at each step, you can either take one or two steps to reach the top.

#### Solution 1: Brute Force DFS (Fibonacci)

class Solution:
    def climbStairs(self, n: int) -> int:
        def climb(n):
            if n == 1 or n == 2:
                return n

            return climb(n - 1) + climb(n - 2)
            
        return climb(n)
        

O(T): O(2^n)
O(S): O(N)

---

The climbStairs method takes an integer n as input, representing the number of stairs to climb. It calculates and returns the number of distinct ways to reach the top of the stairs.

In this approach, two variables, one and two, are initialized to 1. These variables represent the number of ways to climb the stairs for the previous two steps.

The for loop iterates from 0 to n - 2 (since the initial values of one and two already account for the first step). In each iteration, the code updates the values of one and two based on the Fibonacci sequence:

The current value of one is stored in a temporary variable called temp.

one is updated to the sum of its current value and the value of two.

two is updated to the previous value of one stored in the temp variable.

After the loop finishes, the value of one represents the total number of distinct ways to climb n stairs. The method then returns one as the final result.

#### Solution 2: Dynamic Programming

class Solution:
    def climbStairs(self, n: int) -> int:
#         option 1
#         one, two = 1, 1
#         for i in range(n - 1):
#             temp = one
#             one = one + two
#             two = temp

#         return one
          
#         option 2
          dp = [0, 1]
          for i in range(n):
              tmp = dp[1]
              dp[1] = dp[0] + dp[1]
              dp[0] = tmp
        
          print(dp)
          return dp[1]
        

O(T): O(N)
O(S): O(N)