Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Fibonacci Numbers Pattern

A staircase has n steps. You can climb 1, 2, or 3 steps at a time. How many different ways can you reach the top?

n = 3   gives 4 ways:   1+1+1,  1+2,  2+1,  3

Write the obvious recursion and it works. To reach step n you must have come from step n-1, n-2, or n-3, so the answer is the sum of those three counts.

Then run it on n = 40 and it stops finishing. The reason is visible as soon as you draw the calls. Computing ways(38) asks for ways(37), and computing ways(37) asks for it again from a different branch

.....

.....

.....

Like the course? Get enrolled and start learning!