---
tags: data_structure_python
---

# Climbing Stairs <img src="https://img.shields.io/badge/-easy-brightgreen">

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Note:** Given n will be a positive integer.

<ins>**Example 1:**</ins>

>Input: 2
>Output: 2
>Explanation: There are two ways to climb to the top.
>1. 1 step + 1 step
>2. 2 steps

<ins>**Example 2:**</ins>

>Input: 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

# Solution

### Solution 1: Iterative

class Solution:
    def climbStairs(self, n: int) -> int:
        # Fibo.
        a = 0
        b = 1
        
        while n > 0:        
            c = a + b
            a = b
            b = c
            n -= 1
        return c

### Solution 2: Recursive + Memoization

class Solution:
    def climbStairs(self, n: int) -> int:
        # Fibo.
        return self.__climbStairs(n, {})
    
    def __climbStairs(self, n, cache):
        if n in [0, 1]:
            return 1
        elif n in cache:
            return cache[n]
        else:
            res = self.__climbStairs(n-1, cache) + self.__climbStairs(n-2, cache)
            cache[n] = res
            return res