###### tags: `Leetcode` `medium` `greedy` `python` `Top 100 Liked Questions`

# 55. Jump Game

## [題目連結:] https://leetcode.com/problems/jump-game/

## 題目:
You are given an integer array ```nums```. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

Return ```true``` if you can reach the last index, or ```false``` otherwise.

**Example 1:**

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Example 2:**

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

## 解題想法:
兄弟題目: [45. Jump Game II](/XjnNVTJVSWqvC4YHEZMK0A)

* 此題要求判斷是否能跳到last index
* nums[i]表示由i最多可以一次跳nums[i]格
* greedy:
* far_pos紀錄目前所走過的路中，能跳到最遠的位置
* 一路遍歷每格，若該格cur_pos已經>far_pos表示無法再往前了

## Python:

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        far_pos=0
        for cur_pos in range(len(nums)):
            if far_pos>=len(nums)-1:
                return True
            if cur_pos>far_pos:
                return False
            far_pos=max(far_pos,cur_pos+nums[cur_pos])
        return False
        
if __name__ == '__main__':
    result = Solution()
    ans = result.canJump(nums = [2,0])
    print(ans)

#nput: nums = [2,3,1,1,4]
#Output: true