# Climb Stairs

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

## #

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

## #

ImplementationThe 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.

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!