题目描述：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

经典跳跃小游戏，简单的dp缓存表最好想了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//代码如下
	//缓存表
	//dp2是和下面优化的代码有所区分无意义，int类型是因为存三个状态：能到，不能到，未缓存
	int[] dp2;

    public boolean canJump(int[] nums) {
        dp2 = new int[nums.length];
        return f(nums, 0);
    }

    public boolean f(int[] nums, int index) {
       	//basecase
        if (index > nums.length - 1) return false;
        if (dp2[index] != 0) return dp2[index] > 0;
        if (index + nums[index] >= nums.length - 1) return true;

        boolean res = false;
        for (int i = 1; i <= nums[index]; i++) {
            res = res | f(nums, index + i);//去遍历是否有能到的
        }
        dp2[index] = res ? 1 : -1;
        return res;
    }

改动态规划实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//代码如下
	public boolean canJump2(int[] nums) {
        boolean[] dp = new boolean[nums.length];//dp表
        dp[nums.length - 1] = true;
        for (int i = nums.length - 1; i >= 0; i--) {
            //从后往前填写
            if (i + nums[i] >= nums.length - 1) {
                dp[i] = true;//如果可以直接到达则返回true
            } else {
                for (int j = i + 1; j <= i + nums[i]; j++) {
                    //不能的则去遍历能到的位置中有人能达到吗
                    if (dp[j]) {
                        dp[i] = true;
                        break;
                    } else {
                        //剪枝优化：如果不行，那他的后面也不用看了
                        j += nums[j];
                    }
                }
            }
        }
        return dp[0];
    }

额外的，贪心实现：

既然题目要求我们到达最后一个，实际上就是要我们走的越远越好，即当前位置能跳的距离和前面最远的距离的较大值即为当前位置的最远距离，只要大于数组长度就返回true，反之到不了就返回false

1
2
3
4
5
6
7
8
9
//代码如下 非常短    
 public boolean canJump3(int[] nums) {
        int max=0;//当前位置能去的最大值
        for (int i = 0; i <= max; i++) {
            max = Math.max(max, i+nums[i]);
            if (max>=nums.length-1)return true;//max能到了，就返回结束程序运行
        }
        return false;
 }