Leet 코드 70. 계단 오르기

by

당신은 계단을 올라갑니다. 정상에 도달하려면 n걸음이 걸립니다.

매번 1레벨 또는 2레벨을 오를 수 있습니다. 얼마나 많은 다른 방법으로 정상에 오를 수 있습니까?

예 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

예 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

제한:

  • 1<=n<=45

◇ 솔루션

먼저 무의식적으로 4의 경우의 수를 계산합니다. 5의 4와 8의 5… 그것이 피보나치입니다. 죄송해요 뒤늦게 알아 피보나치 수식을 풀 수 있는 방법이 있었는지 어렴풋이 기억이 나네요… 아니 기억이 안나네요. 어떻게 지내세요?

이런저런 글을 쓰기 시작하면서 한 가지가 분명해졌습니다. 재귀를 통해 해결하는 방법을 알아낼 수 없습니다. 재귀를 마지막으로 사용한 것이 언제인지 확실하지 않습니다. 그냥 잊으세요 그러다가 갑자기 문제가 동적 프로그래밍 범주에 있다는 것을 기억했습니다. 해결책을 찾았습니다.

  1. 이전 숫자 변수 제공(n이 얼마인지 모름)
  2. 나중에 숫자 변수를 입력하십시오.
  3. 우리가 찾아야 하는 n은 (n-1 더하기 n-2)입니다.

2개의 변수로만 하려고 했기 때문에 변수에 값을 할당해 보았습니다.

// 첫 번째 시도

var climbStairs = function(n) {
    if (n < 4) return n
    let left = 0
    let right = 1
    while (n > 0) {     
        right = right + left          
        left = right
        n--
    }
    return right
};

생각의 흐름을 덜 따른 결과다. 새 값은 둘의 합이기 때문에 오른쪽 + 왼쪽이고 새 왼쪽 값에 올바른 값을 할당할 수 있지만 결과는 참담한 실패입니다.

그러고 보니 이미 새로운 가치가 부여됐죠? 왼쪽에 넣고 앉았으니 불가능할 수밖에 없었다. a+b=c의 구조에서 a와 b의 값을 알면 bc의 값은 -a가 된다.

// 통과된 답안

var climbStairs = function(n) {
    if (n < 4) return n
    let left = 0
    let right = 1
    while (n > 0) {     
        right = right + left          
        left = right - left
        n--
    }
    return right
};

이렇게 다이나믹프로그래밍으로 문제를 해결했는데 많이 불편하네요. 다른 솔루션을 살펴보겠습니다.

1. 메모이제이션을 사용한 재귀

  • 재귀와 메모이제이션을 오랜만에 보니 코드가 짧네요.
var climbStairs = function(n, memo = {1:1, 2:2}) {
   if (memo(n) !== undefined) return memo(n);   
   memo(n) = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
   return memo(n);
};

2. 재귀

  • 그래 내가 그랬어 (내일이 기억나지 않는다고 했지)
function climbStairs(n) {
    if (n <= 0) return 0;
    if (n === 1) return 1;
    if (n === 2) return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

3. 무차별 대입(DFS) 또는 철저한 검색

  • … 재귀와 동적 프로그래밍이 가능하다고 생각합니다.
/**
 * Brute Force - DFS
 * Time O(2^N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
 var climbStairs = (n, index = 0) => {
    const isBaseCase1 = (n < index);
    if (isBaseCase1) return 0;

    const isBaseCase2 = (index === n);
    if (isBaseCase2) return 1;

    const ( next, nextNext ) = ( (index + 1), (index + 2) );
    const left = climbStairs(n, next);     /* Time O(2^N) | Space O(N) */
    const right = climbStairs(n, nextNext);/* Time O(2^N) | Space O(N) */

    return (left + right);
}

4. 다른 DP(위에서 아래로)

  • 같은 DP, 다른 느낌
/**
 * DP - Top Down
 * Array - Memoization
 * Time O(N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n, index = 0, memo = Array(n + 1).fill(0)) => {
    const isBaseCase1 = (n < index);
    if (isBaseCase1) return 0;

    const isBaseCase2 = (index === n);
    if (isBaseCase2) return 1;

    const hasSeen = (memo(index) !== 0);
    if (hasSeen) return memo(index);

    const ( next, nextNext ) = ( (index + 1), (index + 2) );
    const left = climbStairs(n, next, memo);     /* Time O(N) | Space O(N) */
    const right = climbStairs(n, nextNext, memo);/* Time O(N) | Space O(N) */

    memo(index) = (left + right);                /*           | Space O(N) */
    return memo(index);
};

5. 또 다른 DP (아래에서 위로)

  • 같은 DP라도 저렇게 변합니다.
/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N) | Space O(N)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n) => {
    const isBaseCase = (n === 1);
    if (isBaseCase) return 1;

    const tabu = initTabu(n);/* Space O(N) */

    search(n, tabu);

    return tabu(n);
};

var initTabu = (n) => {
    const tabu = new Array(n + 1).fill(0);

    tabu(1) = 1;
    tabu(2) = 2;

    return tabu;
}

var search = (n, tabu) => {
    for (let index = 3; (index <= n); index++) {/* Time O(N) */
        const ( prev, prevPrev ) = ( (index - 1), (index - 2) );

        tabu(index) = (tabu(prev) + tabu(prevPrev));/* Space O(N) */
    }
}

6. 매트릭스 – 비트넷 방식

  • ???
/**
 * Matrix - Bitnets Method
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
 var climbStairs = (n) => {
    const prev = ( (1, 1), (1, 0) );
    const next = power(n, prev);/* Time O(log(N)) */

    return next(0)(0);
}

const power = (n, prev)  => {
    let next = ( (1, 0), (0, 1) );

    const isEmpty = () => n === 0;
    while (!isEmpty()) {/* Time O(log(N)) */
        const isBit = (n & 1) === 1;
        if (isBit) next = multiply(next, prev);/* Time O(1) | Space O(1) */

        n >>= 1;
        prev = multiply(prev, prev);           /* Time O(1) | Space O(1) */
    }

    return next;
}

const multiply = (prev, next) => {
    const ( rows, cols ) = ( 2, 2 );
    const matrix = new Array(rows).fill()
        .map(() => new Array(cols).fill(0));

    for (let row = 0; (row < rows); row++) {
        for (let col = 0; (col < cols); col++) {
            const left = (prev(row)(0) * next(0)(col));
            const right = (prev(row)(1) * next(1)(col));

            matrix(row)(col) = (left + right);
        }
    }

    return matrix;
}

7. 피보나치 공식

  • 이와 같이?
/**
 * Math - Fibonacci Formula
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/climbing-stairs/
 * @param {number} n
 * @return {number}
 */
var climbStairs = (n, sqrt5 = Math.sqrt(5)) => {
    const phi = ((sqrt5 + 1) / 2);
    const psi = ((sqrt5 - 1) / 2);

    const phiPow = Math.pow(phi, (n + 1));
    const psiPow = Math.pow(psi, (n + 1));

    return ((phiPow - psiPow) / sqrt5);
}

다음 중 귀하의 솔루션은 무엇입니까?