[LeetCode]Jump Game

很简单题，一种解法是类似BFS，
维护一个right bound 每次扫的话更新right bound，如果发现超过了len - 1，则说明可以到，如果当前位置超过了right bound则说明到不了（没有办法到更远了，从头开始到的最远的位置就是right bound）。

代码如下：

值得注意的是，在while循环当中，我们不需要check是否到了len - 1，即是否越界。原因在于，除去len长度为1的情况会return true，长度大于1的时候，分两种情况：

• 如果没有办法跳到len - 1，的话会直接break，更不会越界
• 如果能跳到len - 1，那么最晚在倒数第二个位置即len - 2就会发现right bound会大于等于len - 1，所以会break也不会越界

第二种方法，类似DP的思路，不维护array，从末尾向头部遍历，由于能不能跳过只取决于能否跨过由0造成的gap（gap可能包含非0元素），所以维护一个gap，如果当前A[i] >= gap,则gap reset成1，res设为true（说明从i可以跳到末尾），否则，gap++，res设为false（从i跳不到末尾），所以就看在0的位置res是true还是false。另一方面，gap表示的是从i开始到一个能跳到end的位置的最短距离，如果从i能跳到那个位置，就可以跳到end，否则，无法跳到end，代码如下：