Recursive Staircase Problem

The Problem

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 or 2 stairs at a time. Count the number of ways, the person can reach the top.

The Solution

This is an interesting problem because there are several ways of how it may be solved that illustrate different programming paradigms.

• Brute Force Recursive Solution - Time: O(2^n); Space: O(1)
• Recursive Solution With Memoization - Time: O(n); Space: O(n)
• Dynamic Programming Solution - Time: O(n); Space: O(n)
• Iterative Solution - Time: O(n); Space: O(1)

References

• On YouTube by Gayle Laakmann McDowell
• GeeksForGeeks