[leetcode] Climbing Stairs

아래의 솔루션을 보고 학습했습니다.

 

https://leetcode.com/problems/climbing-stairs/solutions/4211515/0ms-very-easy-beginner-friendly-code-faster-all-three-approaches

---

 

solution 1

Time Complex: O(n)

Space Complex: O(n)

 

function climbStairs(n: number): number {
  if (n <= 1) {
    return 1
  }

  const dp: number[] = new Array(n + 1).fill(-1)
  return climbStairsHelper(n, dp)
}

function climbStairsHelper(n: number, dp: number[]): number {
  if (n <= 1) {
    return 1
  }
  if (dp[n] !== -1) {
    return dp[n]
  }

  dp[n] = climbStairsHelper(n - 1, dp) + climbStairsHelper(n - 2, dp)
  return dp[n]
}

console.log(climbStairs(5))

 

solution 2 (using tabulation)

Time Complex: O(n)

Space Complex: O(n)

function climbStairs(n: number): number {
    const tab: number[] = new Array(n + 1).fill(0);
    if (n >= 0) tab[0] = 1;
    if (n >= 1) tab[1] = 1;
    for (let i = 2; i <= n; i++) 
        tab[i] = tab[i-1] + tab[i-2];
    return tab[n];
}

 

 

solution 3 

Time Complex: O(n)

Space Complex: O(1)

function climbStairs(n: number): number {
    if (n <= 1) return 1;
    let firstNum: number = 1, secondNum: number = 1, thirdNum: number = 0;
    for (let i: number = 2; i <= n; i++) {
        thirdNum = firstNum + secondNum;
        firstNum = secondNum;
        secondNum = thirdNum;
    }
    return thirdNum;
}