---
title: "#55. Jump Game"
tags: LeetCode, Top100
---
#55. Jump Game
==

題目描述
--
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

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.

解題思維
--
可能是DP或遞迴寫得太多，看到題目的第一直覺想先使用這些，思考了一下，我只要去找有沒有方法直接到終點，至於有多少方法或什麼走，不是這個題目的所要思考的，那麼貪婪演算法就很適合處理這個問題。

Greedy Algorithm
--

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)-1
        pos = length
        for i in range(length, -1, -1):
            if i+nums[i] >= pos:
                pos = i

        return pos == 0

Dynamic Programming
--

>從bottom-top檢查是否可以到達。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        dp = [0]*length
        dp[0] = 1
        for i in range(1, length):
            for j in range(i, -1, -1):
                if dp[j] == 0:
                    continue
                if nums[j]+j >= i:
                    dp[i] = 1
                    break

        return dp[length-1] == 1