[LeetCode] Jump Game2

문제

Given an array of non-negative integers, 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.

Example:

Input: [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.

Note:

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

 

Approach

배열 0번째 위치부터 시작해서 현재 위치에서 최대 몇 칸까지 갈 수 있는지 마킹한다.

최대 갈 수 있는 칸에 도달하면 점프 카운터를 올리고 최대 갈 수 있는 칸도 업데이트 한다.

이걸 배열 끝까지 반복한다. 시간복잡도 O(n)

일종의 BFS이다

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_JumpGame2.cpp

chi3236/algorithm