给你一个非负整数数组
nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回
true ；否则，返回 false 。示例 1：
示例 2：
解法一：Top-down DP / 记忆化搜索
每个下标都是一个位置，每个位置都可以跳到右边的一些位置。问有没有一条路径能从
0 走到 n - 1。最直接的思路是从下标
0 开始，把所有能跳到的位置都试一遍。但这样暴力回溯的问题是重复计算太多。对于某个位置
i，一旦我们确定 从 i 出发能到终点 或者 不能到终点，这个结论之后不会改变。无论我们是通过哪条路径来到 i，从 i 往后的数组都一样。于是我们用一个
memo 数组缓存结果：最后一个位置天然是
GOOD，因为它已经在终点。复杂度分析
- 时间复杂度是
O(n^2)
每个位置最多被计算一次，但计算一个位置时，最坏可能扫描它右边的
O(n) 个位置。- 空间复杂度是
O(n)
memo 数组需要 O(n)，递归栈最深也是 O(n)。解法二：Bottom-up DP
如果我能一步跳到某个已经确认能到终点的位置，那我自己也能到终点。
定义：dp[i] 表示 从下标 i 出发，能不能到达最后一个位置,
最后一个位置
dp[n - 1] = True然后从右往左计算。对于位置
i，它能跳到的范围是： [ i + 1 , min(n - 1, i + nums[i]) ]只要这些位置里有一个是
GOOD，那么 i 也是 GOOD。也就是说：
dp[i] = any(dp[j] for j in reachable positions)复杂度分析
- 时间复杂度是
O(n^2)
每个位置最多向右扫描
O(n) 个可达位置。- 空间复杂度是
O(n)
需要一个
dp 数组。解法三：贪心 (最优解)
我们可以从起点往终点搜索，也可以反过来从终点往起点思考。
我们从右往左看，把最后一个下标当成当前目标 ，
goal = n - 1。我们从右往左遍历每个位置
i ：由于
nums[i] 表示从位置 i 最多可以往右跳多少步，如果 i + nums[i] >= goal，则说明从 i 可以跳到当前目标位置。既然当前目标已经能到达终点，那么
i 也能到达终点。于是我们把目标更新为：
goal = i 原来我们需要到达goal，现在只要能到达i就够了，因为i可以到达原来的 goal。
不断这样往左推进。如果最后
goal == 0，说明起点也被证明是 GOOD，可以到达终点。以
nums = [2, 3, 1, 1, 4] 为例：我们从最后一个下标
4 开始把它当作 goal，从右往左看时，发现下标 3 可以到 4，下标 2 可以到 3，下标 1 可以覆盖到 2，下标 0 也可以覆盖到 1，所以 goal 会一路从 4 更新到 0。最终 goal == 0，说明起点本身可以到达终点，因此返回 True。再看一个例子：
nums = [3, 2, 1, 0, 4] ：初始
goal = 4。从右往左看，下标 3 最远只能到 3，下标 2 最远只能到 3，下标 1 最远也只能到 3，下标 0 最远还是只能到 3，所以没有任何位置能跨过下标 3 到达 goal = 4。因此
goal 一直停在 4，最终没有被更新到 0，返回 False。复杂度分析
- 时间复杂度是
O(n)。只需要从右往左遍历一次数组。
- 空间复杂度是
O(1)。只使用了一个变量goal。
总结
这道题可以先从可达性角度理解：每个下标是一种状态，
nums[i] 表示从这里可以跳到右边的一段位置。- 暴力做法是从起点开始 DFS，尝试所有可跳位置；但同一个位置会被不同路径重复访问，所以会超时。
- 对于每个位置，我们缓存它是
GOOD还是BAD：GOOD表示从这里能到终点，BAD表示不能。这样每个位置只会被计算一次，复杂度变成O(n^2)。
- 然后可以把递归改成 bottom-up DP。因为每个位置只依赖它右边的位置，所以从右往左填表。
dp[i]表示从i能否到终点，只要它能跳到某个dp[j] == True的位置，dp[i]就是True。
- 最终的贪心解法来自对 DP 的进一步压缩。Bottom-up DP 需要知道右边哪些位置是 GOOD；贪心发现其实只需要维护最左边的 GOOD 位置。最后只要看 起点（
0）是否能成为最左边的 GOOD 位置。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-55-跳跃游戏
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 46] 全排列
下一篇
[Leetcode 62] 不同路径