DaleStudy | Leetcode Study 2주차 - Climbing Stairs

Leetcode Study

문제

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

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

 

풀이

 

이 문제는 계단을 걸을 수 있는 모든 경우의 수를 구하는 것을 목표로 하고 있다. 

사실 처음 볼 때 어떻게 풀어야할지 감이 안왔는데, 다른 테스트 n=4, n=5를 직접 구해보고 나니 피보나치 수열로 구현하면 되겠다는 생각이 들었다. 문제를 보고 어떻게 풀어야할지 감이 오지 않을 때는, 테스트 코드를 여러개를 만들어 두고 직접 쓰면서 생각해보면 답이 나올 때가 있어서 주로 사용하는 방법이다. 

 

피보나치 수열은 재귀를 이용하면 되는데, 메모이제이션을 하지 않고 구현하면 테스트를 통과하지 못하므로 테스트를 통과하기 위해서는 객체에 값을 저장해나가면서 풀면 된다. 

 

function climbStairs(n: number): number {
    type Cache = {[key: number]: number}

    const cache: Cache = {
        2: 2,
        1: 1
    }

    const fibonacci = (n: number, cache: Cache) => {
        if (n in cache) {
            return cache[n]
        } else {
            cache[n] = fibonacci(n-2, cache) + fibonacci(n-1, cache)
            return cache[n]
        }
    }

    return fibonacci(n, cache);
};

 

 

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