45. &55 Jump Game II

题目要求：

一个数组存储了非负整形数据，数组中的第 i 个元素num[i],代表了可以从数组第i个位置最多向前跳跃nums[i]步；确认可以从第0个位置跳跃到数组最后的位置，求最少的跳跃次数。

Examples：

Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Notion:
You can assume that you can always reach the last index.

解题思路：

• 既然一定可以跳到最后一个元素那里，那么，明确什么时候跳最合适就成了关键！！！
• 每次超过记录的reachable就增加一次跳跃次数

代码：

# pass on leetcode because of time limit
class Solution(object):
    def jump(self, A):
        """
        :param A: List[int]
        :return: int
        """
        jump_count = 0
        reachable = 0
        curr_reachable = 0
        for i, length in enumerate(A):
            if i > reachable:
                return -1
            if i > curr_reachable:
                curr_reachable = reachable
                jump_count += 1
            reachable = max(reachable, i+length)
        return jump_count

if __name__ == "__mian__":
    print(Solution.jump(self=None, A=[2, 3, 1, 1, 4]))