# Question

Formatted question description: https://leetcode.ca/all/45.html

45	Jump Game II

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.

For 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.

@tag-array
@tag-greedy


# Algorithm

The core method is to use Greedy idea of ​​the greedy algorithm to solve it. Think about why? In order to jump to the end quickly, I want to know the range of each step. Greed here is not to choose the position with the farthest jumping power in the range of jumping, because this selection is not necessarily the optimal solution, so to speak it doesn’t feel like a greedy algorithm again.

In fact, what is greedy here is the farthest range that can be reached. It traverses all the positions that can be reached by the current jump, and then predicts the farthest distance that can be jumped in the next step according to the jump force at that position, and greets the farthest range. Once this range reaches the end, the number of steps currently used must be the minimum number of steps.

Two variables cur and pre are required to save the current farthest position that can be reached and the farthest position that can be reached before. As long as cur does not reach the last position, the loop will continue. Pre is first assigned the value of cur, which means the last loop. The farthest position that can be reached later.

• If the current position i is less than or equal to pre, it means that it is still within the range that the previous jump can reach. The current position is added to the jump force to update cur. The method to update cur is to compare the current cur and i + larger value of A[i],
• if it is not stated in the question whether the end can be reached, it can also be judged whether pre and cur are equal at this time. If they are equal, it means that cur has not been updated, that is, the end position cannot be reached, return -1.

# Code

Java

This one is easier to understand, with the break; check

• public class Solution {

public int jump(int[] A) {
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < A.length - 1; i++) { // @note: i < Len - 1. 也就是停在倒数第二个
curFarthest = Math.max(curFarthest, i + A[i]);
if (i == curEnd) {
jumps++;
curEnd = curFarthest;

if (curEnd >= A.length - 1) {
break;
}
}
}
return jumps;
}
}

public class Jump_Game_II {

class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int left = 0; // last jump reaching to
int right = 0; // current jump reaching to

int count = 0;

for (int i = 0; i < nums.length - 1; i++) { // @note: i < Len - 1. 也就是停在倒数第二个
right = Math.max(right, i + nums[i]);
if (i == left) { // reaching furthest of last jump
count++;
left = right;
}
}

return count;
}
}
}

• // OJ: https://leetcode.com/problems/jump-game-ii/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int jump(vector<int>& A) {
int N = A.size();
vector<int> dp(N, INT_MAX);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 1; j <= A[i] && i + j < N; ++j) {
dp[i + j] = min(dp[i + j], 1 + dp[i]);
}
}
return dp[N - 1];
}
};

• class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
pos = 0
ans = 0
bound = len(nums)
while pos < len(nums) - 1:
dis = nums[pos]
farthest = posToFarthest = 0
for i in range(pos + 1, min(pos + dis + 1, bound)):
canReach = i + nums[i]
if i == len(nums) - 1:
return ans + 1
if canReach > farthest:
farthest = canReach
posToFarthest = i
ans += 1
pos = posToFarthest
return ans