70. Climbing Stairs
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?
Note: Given n will be a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step---
Intuition
How can we reach stair n
- One step from n - 1 or
- Two steps from n - 2
# ways to reach n = # ways to reach (n -1) + # ways to reach (n - 2)
F(n) = F(n - 1) + F(n -2)
Recursion with memoization.
We do not need all past entries, just two last ones are sufficient - constant space
--
Time - O(n)
Space - O(1)
Related problems
min-cost-climbing-stairs
