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)