传送门 https://leetcode-cn.com/problems/jump-game/submissions/
题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例：
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
题解：
暴力递归模拟解法（超时）
自顶向下：
在下标为0位置下，有n1个可跳点；n1个的其中一个可跳点中，又有n2个可跳点…如此延伸下去，以下标0位置为树根，其他可跳点为树结点，就构成了一个倒立树状的自顶向下树。
1 | // 自顶向下的递归模拟 |
自顶向下的动态规划解法（超时）
思路：使用记忆表记录位置好坏，优化递归次数（如果可以跳到最后的位置，即好位置；如果不能，就是坏位置）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
enum Index {
good, bad, unknown
}
Index[] memo = null;
public boolean canJumpEnd(int pos, int[] nums)
{
if (memo[pos] != Index.unknown)
{
return memo[pos] == Index.good ? true : false;
}
int longest = Math.min(pos+nums[pos], nums.length-1);
for (int i=pos+1; i<=longest; i++)
{
if (canJumpEnd(i, nums))
{
memo[i] = Index.good;
return true;
}
}
memo[pos] = Index.bad;
return false;
}
public boolean canJump(int[] nums) {
memo = new Index[nums.length];
for (int i=0; i<nums.length; i++)
memo[i] = Index.unknown;
memo[nums.length-1] = Index.good;
return canJumpEnd(0, nums);
}
}
自底向上动态规划解法（不超时，但耗时长）
自底向上：
与自顶向下恰好相反，它是从最底端的树结点向上搜索的方法
思路：
由于已知数组最后一个位置为好位置，所以从数组最后一个位置向上搜索可到达最后一个位置的位置。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
enum Index {
good
}
public boolean canJump(int[] nums) {
int len = nums.length;
Index[] memo = new Index[len];
memo[len-1] = Index.good;
for (int i=len-2; i>=0; i--)
{
int longest = Math.min(i+nums[i], len-1);
for (int j=i; j<=longest; j++)
{
if (memo[j] == Index.good)
{
memo[i] = Index.good;
break;
}
}
}
return memo[0] == Index.good;
}
}
自底向上动态规划 + 贪心（完美的解法）
思路：在自底向上动态规划解法的基础上，使用一个变量记录数组中可到达数组最右位置的最左端位置的下标，避免了二次循环的遍历，节省运行时间。1
2
3
4
5
6
7
8
9
10public boolean canJump(int[] nums) {
// 记录最左端位置，避免二次循环
int lastPos = nums.length - 1;
for (int i=nums.length-1; i>=0; i--)
{
if (i + nums[i] >= lastPos)
lastPos = i;
}
return lastPos == 0;
}
最后，提供个人的粗糙解法
思路：在可跳范围内寻找下一步可跳的最大值（贪心），如果最大值对应位置为0，那么回溯前面的值（回溯）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
if (len == 1)
return true;
int i=0;
while (true)
{
// 数组越界
if (i + nums[i] >= len-1)
return true;
int max = 0;
// 查找最大值
for (int j=i; j<=(i+nums[i]); j++)
{
if (max < nums[j])
max = nums[j];
}
System.out.println(max);
// 逆序定位
for (int j=(i+nums[i]); j>=i; j--)
{
if (max == nums[j])
{
i = j;
break;
}
}
if (i + nums[i] >= len-1)
return true;
else if (i + nums[i] < len -1 && nums[i + nums[i]]==0) // 回溯
{
for (int j=(i+nums[i]); j>=i; j--)
{
if (j + nums[j] >= len-1)
{
System.out.println(j + nums[j]);
return true;
}
}
return false;
}else if (i + nums[i] < len -1 && nums[i]==0) // 示例2情况
{
return false;
}
// 跳一步
i = i + nums[i];
}
}
}
PS：除个人解法外，其余解法来源于力扣官方题解。