Leetcode link: https://leetcode.com/problems/climbing-stairs/
There is a staircase with
n steps. At each step, we can make a decision to either climb 1 or 2 steps.
n steps, find the total number of ways to climb the stairs.
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.
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!