# Climb Stairs

Leetcode link: https://leetcode.com/problems/climbing-stairs/

## Question#

There is a staircase with `n` steps. At each step, we can make a decision to either climb 1 or 2 steps.

Given `n` steps, find the total number of ways to climb the stairs.

Example:

If n = 0, then there is just one way to climb the stairs. You are already on the top.
If n = 1, then you climb 1 step, so just 1 way.
If n = 2, you can climb 1 step at a time, or 2 steps at once. This gives us 2 ways.
If n = 3, then you can climb 1 step, then 2 steps. 2 steps, then 1 step. Or 1 step all the way. Total = 3 ways.

## Implementation#

The key here is to realise that we are making the same duplicate decisions at higher steps. For example, the number of ways to climb when `n = 2 steps`, is the same as when you are on Step 1 of `n = 3`.

Visualising this, we realise that `f(3) = f(2) + f(1)`, where `f` is a function to count the total number of steps. Generalising this, we get `f(n) = f(n-1) + f(n-2)`.

To be efficient, we can store the initial few values and build up our solution from there.

def climbStairs(self, n: int) -> int:
memo = [1,1,2]
if(0 <= n <= 2):
memo[n]
for i in range(3, n + 1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]

To even further optimise the space used, at any point in time, we only need the previous 2 values. We can discard all previous values and just keep track of 2 variables.

By the way, this looks like a solution for fibonacci sequence!