---
# System prepended metadata

title: 55. Jump Game
tags: ['55', leetcode, medium]

---

# 55. Jump Game
###### tags: `leetcode` `55` `medium` 

## :memo:  Question
![](https://i.imgur.com/ZkP4F0x.png)


## :memo: 題意
* 給你一個 nums list，裡面的每個數字代表你在該 index 可以最多往後走幾個位置，問你這個 list，可不可以走到最後一格。

## :memo: My first solution
* :medal: **思考一**: 試試每個走法，backtracking。
```
ex. nums = [2,3,1,1,4]
當到 index = 0 的位置時，可以走的位置就是 1 和 2，如果我走了一步那會到 index = 1，
那 nums[1] = 3，可以走的位置是 1(current position)+1 ~ 1(current position)+3，
以此類推，可以看下圖，藍色的數字代表你走的步數，黑色的數字是你走到的數字。
```
![](https://i.imgur.com/na0MdQD.png)
```
ex. nums = [3,2,1,0,4]
```
![](https://i.imgur.com/OJcnkVe.png)

## :memo: My first solution code
```python=
class Solution:
    def canJump(self, nums: List[int]) -> bool:
    
        if len(nums) == 1:
            return True
            
        visited = [0] * len(nums)

        def dfs(i):
            if visited[-1]:
                return 

            for k in range(nums[i],0,-1):
                if not visited[-1]:
                    if i+k < len(nums):
                        visited[i+k] = 1
                        dfs(i+k)


        for i in range(nums[0],0,-1):
            if not visited[-1]:
                if i < len(nums):
                    visited[i] = 1
                    dfs(i)


        return True if visited[-1] else False
```
這個會過不了，time out


## :memo: leetcode solution
* :medal: **思考一**: greedy，我只在意我目前可以最多可以走到的位置。

ex1.

|  nums | 2 |  3   |  1   |  1   | 4 |
| -------- | -------- | --- | --- | --- | -------- |
|  index        | 0         |  1   |  2   |  3   |   4       |
| max far index    | 2     |  4(1+3) > 2   |   4 > (2+1)   |   4 >= (3+1)  | 4     |

ex2.
|  nums | 3 |  2   |  1   |  0   | 4 |
| -------- | -------- | --- | --- | --- | -------- |
|  index        | 0         |  1   |  2   |  3   |   4       |
| max far index    | 3     |  3(2+1) >= 3   |   3(1+2) >= 3    |  3(0+2) >= 3（所以我走到這時沒有辦法繼續走到下一個了）|      |


## :memo: leetcode solution code
```python=
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        
        for i in range(len(nums)):
            if reach < i:
                return False
            reach = max(reach, i + nums[i])
            
        return True
```

## :memo: BigO
* 時間複雜度: O(len(nums))
* 空間複雜度: O(1)