[리트코드] 70. Climbing Stairs - js (메모이제이션)

1. 문제

https://leetcode.com/problems/climbing-stairs/description/

Climbing Stairs - LeetCode

2. 코드

처음 짠 코드) 타임 아웃

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let count = 0;

    const climb = (total) => {
        if(total === 0) count++;
        else{
            if(total - 1 >= 0)
                climb(total-1);
            if(total - 2 >= 0)
                climb(total-2);
        }
    }

    climb(n);

    return count;
};

정답)

이 문제는 피보나치를 활용하여 풀면 시간 복잡도를 줄일 수 있다. 

예를 들어 계단을 4번 오르는 데에는 총 5가지 방법이 있다.

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

계단을 3번 오르는 데에는 총 3가지 방법이 있다.

1 1 1
1 2
2 1

계단을 2번 오르는 데에는 총 2가지 방법이 있다.

1 1
2

계단을 4번 오르는 방법에 2번과 3번 오르는 과정이 중복된다. 그래서 피보나치를 통해 이전 값을 메모이제이션해두면 시간 복잡도를 줄 일 수 있게 되는 것이다.

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n < 4) return n;
    let fib = [1, 1];
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    return fib[n];
};