LeetCode : 55. Jump Game 跳游戏

- 日理万妓 2021-06-24 16:11 341阅读 0赞

**试题**  
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: \[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: \[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.

**代码**  
这一题最好想的就是动态规划，明显从前面往后跳会出现多种可能的情况。但是从后往前想我们就知道，我们只需要知道是否能够跳到当前点，而无需知道有多少种方式。

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

贪心：如果i能到lastPos的话，那我们只需要判断是否能到达i。有人可能会想万一有路径直接越过i到达lasPos的呢？其实如果有路径能够越过i到达lasPos，那也就意味着这个路径是可以到达i的。因为我们只需判断是否能够达到，而不需要考虑跳的次数。另外一种想法，如果我们在直线上把所有的点能跳的范围画出来，那么只有一种情况导致不能跳到最后，那就是存在一个点不可达。

class Solution {
        public boolean canJump(int[] nums) {
            if(nums==null || nums.length==0) return false;
            int len = nums.length;
            int lastPos = len-1;
            
            for(int i=len-2; i>=0; i--){
                if(lastPos-i<=nums[i]){
                    lastPos = i;
                }
            }
            return lastPos==0?true:false;
        }
    }