(Leet Code JS)Jump Game II

https://leetcode.com/problems/jump-game-ii/

Jump Game II - LeetCode

DP 알고리즘 사용.

dp 배열을 nums의 length 만큼 선언하고, Infinity로 초기화 한다.

시작은 0번째 인덱스부터 시작하기 때문에

dp[0] = 0으로 저장하고 for문을 시작한다.

 

nums 배열을 순회.

nums[i]는 점프할 수 있는 최대 거리를 나타내기 때문에 이중 for문으로 끝까지 갈 수 있는 최소 횟수를 dp에 갱신하면 된다.

 

거리는 1 ~ nums[i]기.

dp는 해당 인덱스에 도달하기 위한 최소 횟수가 저장되어 있다.

그렇기 때문에 점프를 시도하면 dp[i] + 1과 dp[i + 점프 거리]를 비교하여 더 작은 값을 dp에 갱신한다.

만약 점프 거리가 length와 같거나 크다면 진행할 수 없기 때문에 break한다.

그렇지 않다면 점화식을 이용해 dp를 갱신한다.

 

리턴값은 dp[length - 1]을 하면 된다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    const length = nums.length;
    const dp = Array(length).fill(Infinity);
    
    if(length === 1){
        return 0;
    }
    
    dp[0] = 0;
    
    for(let i = 0; i < length; i++){
        const distance = nums[i];
        const next = dp[i] + 1;
        
        for(let j = 1; j <= distance; j++){
            if(i + j >= length){
                break;
            }
            dp[i + j] = Math.min(next, dp[i + j]);
        }
    }
    
    return dp[length - 1];
};