:orphan:

Climbing Stairs
===============

.. highlight:: none

Problem
-------
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``

.. highlight:: python

Pattern
-------
Math, Dynamic Programming, Memoization

Solution
--------
Let's start at the top and work backwards. If we are at the top, our last move
must be either a 1 or a 2 step jump. Thus ::

    climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)

Code
----

.. literalinclude:: ../problems/easy/climbing-stairs/climbing_stairs__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from climbing_stairs__approach_1 import climbStairs
>>> climbStairs(2)
2
>>> climbStairs(3)
3

Complexity
----------
| Time: :math:`O(n)` — each value from 1 to n is calculated once
| Auxiliary Space: :math:`O(n)` — dictionary stores each value from 1 to n

.. autofunction:: climbing_stairs__approach_1.climbStairs