LeetCode 55 - Jump Game (Medium)

문제

LeetCode - 55번

풀이 과정

현재 위치에서 움직일 수 있는 거리가 주어져있고, 이를 통해 마지막 위치 도달 가능성을 판단하는 동적 계획법 문제입니다.
따라서 dp(x) = x에서 마지막 index에 도달 가능한지 여부 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다.

dp(x) = at least one for all dp(x + jump) , 이때 jump는 x에서 점프 가능한 거리

즉, 현재 위치에서 도달 가능한 위치 중 어느 하나라도 마지막 위치에 도달하는 경로를 가지고 있다면
현재 위치에서도 마지막에 도달할 수 있는 것입니다.

Javascript 에서는 함수형 프로그래밍 기법에 기반한 메모이제이션 패턴이 있습니다.
이번 문제에서는 클로저 를 활용해서 Top-down 방식의 메모이제이션을 구현해봤습니다.

다른 사람들의 풀이를 보니 미리 고정된 Array 를 사용하거나 Map 자료구조를 활용하는 방법도 제시되고 있는데
그중 가장 일반적으로 사용하는 방식(Object 사용)을 적용했습니다.

코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */

var canJump = function (nums) {
  let cache = {};
  const dp = function (x) {
    if (x >= nums.length) {
      return 0;
    } else if (x === nums.length - 1) {
      return 1;
    }

    if (x in cache) {
      return cache[x];
    }

    cache[x] = false;
    for (let jump = 1; jump <= nums[x]; jump++) {
      cache[x] |= dp(x + jump) ? 1 : 0;
    }

    return cache[x];
  };

  return dp(0);
};

const nums = [2, 0];
console.log(canJump(nums));

Javascript 메모이제이션 참고자료

• https://www.freecodecamp.org/news/understanding-memoize-in-javascript-51d07d19430e/
• https://soldonii.tistory.com/97