55. 跳跃游戏 (opens new window)

1.DFS

解题思路：用visited数组保存使用位，如果当前位置已经跳过，那么从其它起跳点也能到达该位置的搜索分支，则不需要继续进行搜索(已经搜索过)。

class Solution {
    boolean res=false;
    public boolean canJump(int[] nums) {
        int[] visited=new int[nums.length];
        dfs(nums,visited,0);
        return res;
    }
    public void dfs(int[] nums,int[] visited,int index){
        if(visited[index]==1) return;
        visited[index]=1;
        if(index==nums.length-1||index+nums[index]>=nums.length-1){
            res=true;
            return;
        }
        if(nums[index]==0) return;
        for(int i=index+1;i<=index+nums[index];i++){
            dfs(nums,visited,i);
        }

    } 
}

2.贪心——保存最大可达位置

每次跳跃时，保存当前能够到达的最远的位置k，如果当前遍历索引指针i比k大，说明i这个位置永远到不了，返回false。

class Solution {
	public boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}