跳跃游戏

怎样从“nums=[2,3,1,1,4],判断能否从 0 跳到最后一格。”推导出 贪心 · 可达性，并证明每次状态变化都不会漏掉答案？

中心结论：维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。

给定一个非负整数数组，最初位于数组的第一个位置。数组中的每个元素代表在该位置可以跳跃的最大长度。判断是否能够到达最后一个位置。

在本站主例中，nums=[2,3,1,1,4],判断能否从 0 跳到最后一格。

算法最终需要得到或观察：farthest 至少到 4,可达 true。

枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“局部最优路标”，明确答案需要观察什么。
2. 2状态只维护 farthest、当前 i。
3. 3转移每一步按照 维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。
4. 4收尾读取 farthest 至少到 4,可达 true。，并复核边界与复杂度。

局部选择必须带着“替换任何其他选择都不会更差”的证明。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：farthest、当前 i。

给出一个非负数组，要求判断从数组 0 下标开始，能否到达数组最后一个位置。 这一题比较简单。如果某一个作为 `起跳点` 的格子可以跳跃的距离是 `n`，那么表示后面 `n` 个格子都可以作为 `起跳点`。可以对每一个能作为 `起跳点` 的格子都尝试跳一次，把 `能跳到最远的距离maxJump` 不断更新。如果可以一直跳到最后，就成功了。如果中间有一个点比 `maxJump` 还要大，说明在这个点和 maxJump 中间连不上了，有些点不能到达最后一个位置。

维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。

执行过程中持续维护：farthest、当前 i。

正确性依赖以下不变量：farthest 是扫描前缀内可达的最远下标。

面试时可以压缩为：一趟维护 farthest,i>farthest 即 false,否则更新,O(n)。

落到当前题，执行机制可以压缩为：维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[2,3,1,1,4],判断能否从 0 跳到最后一格。 因为：维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。
2. 2维护最远可达位置 reach扫描每个下标。 因为：贪心:只关心最远能到哪。
3. 3i=0,最远可达更新为 2更新全局最远可达。 因为：只要 reach 覆盖末下标即可 true。
4. 4i=1,最远可达更新为 4更新全局最远可达。 因为：只要 reach 覆盖末下标即可 true。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6可以到达最后一个下标返回 true。 因为：O(n) 一次扫描。
7. 7维护最远可达位置 reach扫描每个下标。 因为：贪心:只关心最远能到哪。
8. 8收尾与复杂度farthest 至少到 4,可达 true。 因为：时间 O(n) · 空间 O(1)。维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func canJump(nums []int) bool {
	n := len(nums)
	if n == 0 {
		return false
	}
	if n == 1 {
		return true
	}
	maxJump := 0
	for i, v := range nums {
		if i > maxJump {
			return false
		}
		maxJump = max(maxJump, i+v)
	}
	return true
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="jump-game", nums=[2,3,1,1,4]
    //    期望：farthest 至少到 4,可达 true。
    //
    // 2. 失败 / 未命中
    //    检查：DP 可做但贪心 O(n)/O(1) 足够。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC45 最少跳跃；LC130 被围区域
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[2,3,1,1,4],判断能否从 0 跳到最后一格。
2. 2重复枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。
3. 3优化维护 farthest:若 i>farthest 失败,否则 farthest=max(farthest,i+nums[i])。
4. 4证明farthest 是扫描前缀内可达的最远下标。
5. 5复杂度时间 O(n)，空间 O(1)