Leetcode - 계단 오르기 (JavaScript 포함)

오늘은 Climbing Stairs 알고리즘 문제를 해결하는 방법을 보여 드리겠습니다.

문제는 다음과 같습니다.


이 문제에 대한 해결책을 더 잘 이해하는 데 도움이 되는 트리를 만들 것입니다.

4계단의 꼭대기까지 올라갈 수 있는 서로 다른 방법의 수를 알아봅시다.

우리가 취할 수 있는 단계의 수에 따라 트리에 가지를 추가할 것입니다. 이 문제에서는 1단계 또는 2단계를 수행할 수 있습니다. 1보를 내딛으면 3보를 더 올라야 합니다. 2걸음 하면 2걸음 남습니다. 기본 사례에 도달할 때까지 분기를 계속 추가합니다.

계단이 0인 경우 오를 수 있는 방법은 몇 개입니까? 한 가지 방법이 있습니다. 그냥 오르지 않는 것입니다.

계단이 1개일 때 오를 수 있는 방법은 몇 개입니까? 한 가지 방법이 있습니다. 바로 그 한 단계를 오르는 것입니다.

계단을 오르는 총 방법 수를 계산하려면 먼저 바닥부터 시작하여 각 계단에 도달하는 방법의 수를 파악해야 합니다. 그런 다음 각 단계의 방법 수를 더하면 4단계 계단을 오르는 데 총 5가지 방법이 있음을 알 수 있습니다.



이제 우리는 이 문제에 대한 해결책이 하위 문제의 합임을 알 수 있습니다. 우리의 경우 4단 계단을 오르는 총 방법 수는 3단 계단과 2단 계단을 오르는 총 방법의 합입니다. 이를 기반으로 다음과 같이 작성할 수 있습니다.
num_ways(4) = num_ways(3) + num_ways(2)
n개의 단계에 대해 방정식은 다음과 같습니다.
num_ways(n) = num_ways(n-1) + num_ways(n-2)

이것은 실제로 피보나치 수열입니다. 피보나치 수열의 각 숫자는 0과 1부터 시작하여 앞선 두 숫자의 합입니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
피브(n)=피브(n-1)+피브(n-2)

따라서 해결책은 다음과 같습니다.

var climbStairs = function(n) {
    if (n == 1 || n == 0) return 1 // our base cases

    let first = 1;
    let second = 2;

    for (let i = 3; i <= n; i++) {
        let third = first + second;
        first = second;
        second = third;
    }
    return second;

};