Climbing Stairs

Loading...LeetCode

Problem

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

• Total - O(1)