**By: Saurav**

**2017-11-11 22:30:00 UTC**

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?

Example :

Input : 3

Return : 3

Steps : [1 1 1], [1 2], [2 1]

This problem looks tough and feels like where to start but its actually very simple if you follow a simple strategy to solve problems:

Divide and conquer!!

Lets solve the problem for very small number of stairs and we will use memoization techniques to solve the next problem. You will see this is just a Fibonacci sequence.

I have tried to visualize what pattern I saw in the figure below:

As indicated, each ways for given step number (after 2 steps), is the sum of the last two ways.

If you think about combinations, you will feel it makes sense:

Suppose we are given: 1 and (11,2) and I want to know number of combinations possible by combining them:

Number of combinations possible = 11(1), 2(1), (1)2.

Lets write some tests first:

**Attempt 1:**

All our tests pass.

Its time to refactor our code, make it clean and let one function do just one thing best.

All our tests pass and each function does one thing and just one thing best.

Let me know what you think!

twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)