Leetcode Link: 55. 跳跃游戏 - 力扣（LeetCode）
题目
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标
解法一
思路：主要根据题目的特殊性来的
题目中提到两个关键信息：
- 开始位于第一个下标，意味着必需从第一个位置开始走
- 数组中的每个元素代表你在该位置可以跳跃的最大长度，表示我走
[1, 最大长度]的步数都可以
第 2 点意味着什么？ 意味着只要数组中没有 0，我不用管元素值是多少（或者说每个位置允许我走多少，反正题目中不让取负值，也就是说我不用往回走），我一步一步走早晚能走到终点！
那么可以肯定的是，当数组中没有 0 时，我肯定能走到末尾
如果遇到 0，该怎么办？ 遇到 0 了，往前看，如果前面的所有位置元素不能跨过这个 0，说明我无论如何也不能跨过这个 0。 能不能跨过这个位置的0，就需要考虑该位置之前的所有位置能走的最大长度了。
题解：
class Solution:
def canJump(self, nums: List[int]) -> bool:
p = 0
# 注意这里如果 p 取到了 len(nums)-1 就说明走到尾巴了
# 这里不用判定p是不是越界，
while(p < len(nums)-1):
if nums[p] != 0:
p += 1
else:
# 找到了一个0，需要往前看有没有哪个位置能跳过这个0的
# 假定 0 这个位置为 stone
stone = p
while(1):
p -= 1 # 往前看
if p < 0: # 没有能跳过这个0的，所以不可能跳到末尾
return False
if nums[p] > stone - p:
# 找到了可以跳过去的，就把p重置回0位置的下一个继续
p = stone + 1
break
return True解法二
思路：贪心，是随想录的方法，换一种说法（随想录思路看这里）
每个格子上都跳最大的长度，记录并更新最远的覆盖范围，如果这个覆盖范围能覆盖到最后的点，就说明可以了。
分解成了每个位置上往前跳的子问题，每个子问题都取最远的长度（但这是最优嘛？感觉怪怪的），然后看看最终照着最远的长度能不能覆盖到最后
实际上也离不开遍历每个点，没法只看当前格子和当前格子能跳的最远格子
- 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
- 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
- 如果可以一直跳到最后，就成功了
题解：
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0 # 最远覆盖
p = 0
while(1):
if p > cover: # p 超过了最远覆盖，说明到不了末尾
return False
cover = max(cover, p+nums[p]) # p+nums[p]是当前点p的最远覆盖范围
if cover >= len(nums)-1:
return True
p += 1 # p 往下走
启发和联系
我开始甚至想用回溯来做…应该是可以用回溯来做的，我产生了路径依赖所以没选择回溯