LeetCode 55. Jump Game

[Woodyiiiiiii]

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.

Determine if you are able to reach the last index.

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 <= 3 * 10^4
• 0 <= nums[i][j] <= 10^5

---

这道题我一开始就想到用DP来做，dp[i]代表能否跳到第i个位置，状态转移方程是能否找到i之前的能到达i：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] == 1 && nums[j] + j >= i) {
                    dp[i] = 1;
                    break;
                }
            }
            if (dp[i] == 0) return false;
        }
        return dp[n - 1] == 1 ? true : false;
    }
}

虽然Accepted了，但是时间复杂度是O(n^2)平方级别，过于复杂了，我们尝试把它简化一下。

我们可以想到，状态转移方程中，我们没必要迭代i之前的所有元素，只需要关心i - 1位置的元素就行了，因为跳力是随i的递增而递减的。换句话说，我们从dp[i - 1]和nums[i - 1]中的跳力挑出最大值然后减一就可以了，即：dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;

class Solution {
    public boolean canJump(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return true;
    }
}

实际上，题目真正的意思是要我们利用贪婪(Greedy)法的思想。
我们只需要关心当前能跳到的最远值就可以了，创建一个变量limit表示能跳到的最远位置：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length, limit = nums[0];
        for (int i = 1; i < n; ++i) {
            if (limit >= n - 1) return true;
            if (i > limit) return false;
            limit = limit >= nums[i] + i ? limit : nums[i] + i;
        }
        return true;
    }
}

---

类似题目：

• 45. Jump Game II

参考资料：

• https://leetcode.com/problems/jump-game/
• [LeetCode] 55. Jump Game grandyang/leetcode#55