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

## :memo: Question

## :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，
以此類推，可以看下圖，藍色的數字代表你走的步數，黑色的數字是你走到的數字。


ex. nums = [3,2,1,0,4]


## :memo: My first solution code

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

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)