55.Jump Game
===

###### tags: `Medium`,`Array`,`DP`,`Greedy`

[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.

**Constraints**:

* 1 <= `nums.length` <= 10^4^
* 0 <= `nums[i]` <= 10^5^

### 解答

#### Javascript

function canJump(nums) {
  let max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (i > max) return false;
    max = Math.max(max, i + nums[i]);
  }

  return true;
}

>[name=Marsgoat][time= Dec 26, 2022]

#### Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last = len(nums) - 1
        for i, num in reversed(list(enumerate(nums))):
            if i + num >= last:
                last = i
        return last == 0

> 來點反向思維
> [name=Yen-Chi Chen][time=Mon, Dec 26, 2022]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        #can_reach_end = [0]*len(nums)
        #can_reach_end[-1] = 1
        
        last_can_reach = n-1
        for idx in range(n-2, -1, -1):
            if idx+nums[idx] >= last_can_reach:
                #can_reach_end = 1
                last_can_reach = idx
        
        if last_can_reach != 0:
            return False
        else:
            return True

> 一開始寫DFS 笑死 越想越不對勁
> [name=玉山][time=Mon, Dec 26, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)