Leetcode 45. Jump Game II

a처음에는 재귀를 이용한 완전 탐색으로 접근했다.

/**
 * @param {number[]} nums
 * @return {number}
 */
const jump = function(nums) {
    const endIndex = nums.length - 1
    let ans = Infinity

    function travel(position, count) {
        if (position > endIndex) {
            return
        }
        if (position === endIndex) {
            ans = Math.min(ans, count)
            return 
        }
        const jumpRange = nums[position]
        for (let i = 1; i <= jumpRange; i++) {
            travel(position + i, count + 1)
        }

    }
    travel(0, 0)
    return ans
};

 

시간 복잡도를 줄이기 위해 배열을 하나 선언했고, 그 배열을 업데이트하면서 재귀를 개선하였다. (메모이제이션)

 

const jump = function(nums) {
    const memo = Array(nums.length).fill(0);
    let min = Infinity
    function run(idx) {
        if (idx >= nums.length - 1) return 0 
        if (memo[idx]) return memo[idx]

        for (let i = idx + 1; i <= idx + nums[idx]; i++) {
            min = Math.min(min, run(i) + 1)
        }

        memo[idx] = min

        return min
    }

    console.log(memo)
    return run(0)
};

 

마지막으로, dp로도 가능하다.

 

const jump = function(nums) {
    const dp = new Array(nums.length).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 0; i < nums.length; i++) {
        const maxJump = Math.min(i + nums[i], nums.length - 1);
        for (let j = i + 1; j <= maxJump; j++) {
            dp[j] = Math.min(dp[j], dp[i] + 1);
        }
    }
    return dp[nums.length - 1];
};