You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation:
There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 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
Pseudocode
establish some relationship with each increase in step, find a general pattern
n = 4
1. 1 step + 1 step + 1 step + 1 step ...(3 steps)
2. 1 step + 2 steps + 1 step ...(3 steps)
3. 2 steps + 1 step + 1 step ...(3 steps)
4. 1 step + 1 step + 2 steps ...(2 steps)
5. 2 steps + 2 steps ...(2 steps)
to get to 4 steps
- increase the number of ways to get to 3 steps + 1 step to 4 steps
- increase the number of ways to get to 2 steps + 2 steps to 4 steps
ways(n) = ways(n - 1) + ways(n - 2)
for other dp solutions see:
https://leetcode.com/problems/climbing-stairs/solutions/1792723/python-in-depth-walkthrough-explanation-dp-top-down-bottom-up/?orderBy=most_votes
Solution
var climbStairs = function (n) {
if (n <= 3) {
return n;
}
let a = [1, 2];
for (let i = 3; i <= n; i++) {
console.log(a);
a = [a[1], a[0] + a[1]];
}
return a[1];
};
Time and Space Complexity
Time
loops over from 3 to n - O(N), summation assignment O(1)
Total - O(N)
Space
assignment to 2 element array in every loop - O(1) always two elements, doesn't expand with input
