55 & 45. Jump Game I & II

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 104

• 0 <= nums[i] <= 105

My Solutions:

用一个变量记录在当下可以达到的最远距离。在遍历完数组之后，检查这个最远距离是否达到数组的长度-1（数组最后一个数字）。

public boolean canJump(int[] nums) {
    int max = nums[0], len = nums.length;
    if (len == 1) return true;

    for (int i = 1; i < len; i++) {
        if (max < i) return false; // 这一步必须先检查，看当前的位置能否到达
        max = Math.max(max, i + nums[i]);
    }

    return max >= len - 1;
}

45. Jump Games II

类似的题目，但是要返回 minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: 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
Explaination: 从2跳到3，再从3跳到4

My Solutions:

方法1: DP

public int jump(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len];

    for (int i = 1; i < len; i++) { // 因为已经站在第一个位置上，所以从第二个位置开始
        
        // 每到达一步需要的最多步数，比如到index1至少需要跳一步；在index4至少需要跳四步
        dp[i] = i; 
        
        for (int j = 0; j <= i; j++) {
            //如果从j位置可以跳到i位置
            if (nums[j] + j >= i) { 
                dp[i] = Math.min(dp[j] + 1, dp[i]);
            }
        }
    }
    
    return dp[len - 1];
}

方法2: 贪心。如果想要步数最小，需要每一步都跳的很大。在遍历数组的时候，确定当前最远能跳到的位置，记录为max。如果当前的位置超过了上一次算出的最大位置（lastJumpMax)，那么更新lastJumpMax，同时更新步数，因为必须要多一跳才能继续前进。

public int jump(int[] nums) {
    int steps = 0, max = 0, lastJumpMax = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        max = Math.max(max, i + nums[i]);
        if (i == lastJumpMax) {
            lastJumpMax = max;
            steps++;
        }
    }
    return steps;
}