45. Jump Game II

greedy

time: O(n)

space: O(1)

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)

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，最少需要跳幾次
```