跳跃游戏
问题
给定一个非负整数数组，您最初位于数组的第一个索引。数组中的每个元素代表您在该位置的最大跳跃长度。
确定您是否能够到达最后一个索引。
示例 #1
输入: [2,3,1,1,4]
输出: true
解释: 从索引 0 跳跃 1 步到索引 1，然后跳跃 3 步到达最后一个索引。
示例 #2
输入: [3,2,1,0,4]
输出: false
解释: 无论如何，您总是会到达索引 3。其最大跳跃长度为 0，这使得无法到达最后一个索引。
命名
我们将数组中的一个位置称为"好索引"，如果从该位置开始，我们可以到达最后一个索引。否则，该索引被称为"坏索引"。问题随后简化为索引 0 是否是"好索引"。
解决方案
方法 1：回溯
这是低效的解决方案，我们尝试每一种可能的跳跃模式，这些模式将我们从第一个位置带到最后一个位置。我们从第一个位置开始，并跳转到可以到达的每一个索引。重复此过程直到到达最后一个索引。当卡住时，回溯。
参见 backtrackingJumpGame.js 文件
时间复杂度：：O(2^n)。
从第一个位置到最后一个位置有 2^n（上界）种跳跃方式，其中 n 是数组 nums 的长度。
辅助空间复杂度：O(n)。
递归需要额外的栈帧来存储。
方法 2：动态规划自顶向下
自顶向下的动态规划可以被认为是优化的回溯。它依赖于这样一个观察结果：一旦我们确定了某个索引是好的/坏的，这个结果将永远不会改变。这意味着我们可以存储结果，而不需要在每次重新计算时都重新计算。
因此，对于数组中的每个位置，我们记住这个位置是好的还是坏的。让我们称这个数组为 memo，并且它的值要么是 GOOD，BAD，UNKNOWN 中的一个。这种技术被称为 memoization。
参见 dpTopDownJumpGame.js 文件
时间复杂度：：O(n^2)。
对于数组中的每个元素，比如 i，我们正在查看其右侧的 nums[i] 元素，以寻找一个好的索引。nums[i] 最多可以是 n，其中 n 是数组 nums 的长度。
辅助空间复杂度：O(2 * n) = O(n)。
首先 n 来自递归。其次 n 来自 memo 表的使用。
方法 3：动态规划自底向上
通过消除递归，从自顶向下的方法转换为自底向上的方法。实际上，这样做可以获得更好的性能，因为我们不再有方法的堆栈开销，并且甚至可能从中受益于一些缓存。更重要的是，这一步为未来的优化开辟了可能性。通常通过尝试逆转自顶向下方法中的步骤顺序来消除递归。
这里的观察是，我们只跳转到右边。这意味着如果我们从数组的右侧开始，每次我们查询其右侧的位置时，那个位置已经被确定为是好是坏。这意味着我们不再需要递归了，因为我们会始终击中 memo 表。
参见 dpBottomUpJumpGame.js 文件
时间复杂度：：O(n^2)。
对于数组中的每个元素，比如 i，我们正在查看其右侧的 nums[i] 元素，以寻找一个好的索引。nums[i] 最多可以是 n，其中 n 是数组 nums 的长度。
辅助空间复杂度：O(n)。
这来自 memo 表的使用。
方法 4：贪心
一旦我们在底部状态中有了代码，我们可以做出一个最后的、重要的观察。从给定的位置开始，当我们试图看看我们是否能跳到一个好位置时，我们只使用一个 - 最左边的一个。换句话说，最左边的一个。如果我们跟踪这个最左边的好位置作为一个单独的变量，我们就可以避免在数组中搜索它。不仅如此，而且我们可以完全停止使用数组。
参见 greedyJumpGame.js 文件
时间复杂度：：O(n)。
我们对 nums 数组进行单次遍历，因此有 n 步，其中 n 是数组 nums 的长度。
辅助空间复杂度：O(1)。
我们没有使用任何额外的内存。