[리트코드] 45. Jump Game II / Javascript

문제주소 :https://leetcode.com/problems/jump-game-ii/

---

<문제 설명>

45. Jump Game II

Medium

5835222Add to ListShare

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

 

Example 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4] Output: 2

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

 

<풀이법>

▒ 한줄 개념: dp ▒ 

기본적인 dp 문제 중 하나입니다.

문제 풀이법은 다음과 같습니다.

 

1. dp 배열 생성

2. nums를 반복문으로 탐색

  2-1. num값 만큼 반복문을 진행하며 경우 확인 (num = 2일 경우, 1칸 뛰었을 때/2칸 뛰었을 경우 존재)

  2-2. n만큼 점프한 칸의 값(dp[i+n])이 현재 칸까지의 최소 점프횟수 + 1(dp[i]+1) 보다 클 경우, 값 갱신(dp[i+n] = dp[i]+1)

3. dp의 마지막 값을 반환

 

<코드(Javascript)>

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    const dp = [0];
    for(let i = 1; i < nums.length; i++){
        dp[i] = Number.MAX_VALUE;
    }
    
    nums.map((num, i) => {
        for(let j = 1; j <= num && i+j < nums.length; j++){
            dp[i+j] = dp[i] + 1 < dp[i+j] ? dp[i] + 1 : dp[i+j];
        }
    })
    
    return dp[nums.length - 1];
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest