LeetCode 70 - Climing Stairs (Easy)

문제

LeetCode - 70번

풀이 과정

전형적인 동적 계획법 문제입니다.

현재 계단에서 올라갈 수 있는 칸의 수가 1~2 이므로
dp(n) = n번째 계단에서 마지막 계단에 도달하는 경우의 수 라고 정의한다면
다음과 같은 점화식을 얻을 수 있습니다.

dp(n) = dp(n-1) + dp(n-2)

이는 피보나치 수열과 같은 형태를 가지고 있는 것을 알 수 있네요.

이번 문제에서는 보통 Javascript로 메모이제이션을 구현할 때 주로 사용하는 클로저 패턴이 아니라
다른 언어에서 사용하는 전역 스코프 변수를 미리 할당받아 사용하였습니다.

이후 문제부터는 Javascript 에 익숙해지기 위해 메모이제이션을 구현할 때 클로저를 활용할 예정입니다.

코드

/**
 * @param {number} n
 * @return {number}
 */
let memo = new Array(46).fill(-1);

var climbStairs = function (n) {
  if (n === 0) {
    return 1;
  } else if (n < 0) {
    return 0;
  }

  if (memo[n] !== -1) {
    return memo[n];
  }

  memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
  return memo[n];
};