# 45. Jump Game II

![](/files/-MhsSxGcmF3C1ns0vXsC)

![](/files/-MhsT-18a_NsVURR3JVY)

## greedy

time: O(n)

space: O(1)

```java
class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0; // notice this corner case, only one element, no jumps
        int start = 0;
        int end = 0;
        
        int step = 0;
        while (start <= end) {
            int newEnd = end;
            for (int i = start; i <= end; i++) {
                newEnd = Math.max(newEnd, i + nums[i]);
                if (newEnd >= nums.length - 1) {
                    return step + 1;
                }
            }
            step++;
            start = end + 1;
            end = newEnd;
        }
        
        return -1;
    }
}

/*
    like BFS simple version
    while (start <= end) { => like if (!q.isEmpty()) , this is a new way but the same idea
    
    
    in each level, find the next level new candidates ( find next level's newEnd )
    new element will generate new end boundry, until reach the end, return the step+1
    (xxx) [xxx] (xxxx)
*/
```

## implicit BFS version

not easy to think, give it up

## dp - dfs + memo

O(n^2)

```java
class Solution {
    public int jump(int[] nums) {
        Integer[] memo = new Integer[nums.length];
        return dfs(nums, 0, memo);
    }

    private int dfs(int[] nums, int start, Integer[] memo) {
	if (start >= nums.length - 1) {
	    return 0;
	}
        if (memo[start] != null) {
            return memo[start];
        }
        
	// cant use Integer.MAX_VALUE, will overflow, so use Integer.MAX_VALUE/2
        int min = Integer.MAX_VALUE/2; 
        
        // i <= 最多可以走到哪裡
	for (int i = start + 1; i <= nums[start] + start; i++) {
	    min = Math.min(min, 1 + dfs(nums, i, memo)); // here 1 + Integer.MAX_VALUE/2
	}
        
        memo[start] = min;
	return memo[start];
    }
}
```

n^2 思路

````
```java
// [2,3,1,1,4]
nums[]




base case -> idx == n-1

index + 1,
index + 2,

memo[position] -> min jump

for (i =  1 to nums[index]) { // this one
    dfs(idx + i)+1
}

     2 (1 to 2)
    / \
    1  2
    /. \
     

     T: O(n^2)



     // [2,3,1,1,4]
// dp[i] := 從起點到 i，最少需要跳幾次
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/45.-jump-game-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.