Introduction to Fibonacci Numbers Pattern

A staircase has N steps. You may climb one, two, or three steps at a time. How many different ways reach the top?

N = 3

1 + 1 + 1
1 + 2
2 + 1
3

answer = 4

To reach step N, the final move came from step N - 1, N - 2, or N - 3.

This gives a correct recursive rule:

ways(N) = ways(N - 1) + ways(N - 2) + ways(N - 3)

Plain recursion calculates the same smaller answers many times.

Dynamic Programming stores each answer once. Start with the smallest positions and build toward N.

ways(0)=1, ways(1)=1, ways(2)=2, ways(3)=4, ways(4)=7