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?

climbing-stairs.js

export function climbStairs(nums) {
  const dp = Array.from(nums).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  // ways to reach step i = ways to reach step i-1 + ways to reach step i-2
  for (let i = 2; i <= nums; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[nums];
}

// tc: O(n) (can be improved with another approach to O(logn))
// sc: O(n) (can be improved to O(1))