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

## :memo: Question

## :memo: 題意
* 跟 55 題 jump game 的題目差不多，給你一個 nums list，裡面的每個數字代表你在該 index 可以最多往後走幾個位置，這個 list 一定可以走到最後，然後問你走到最少可以走幾步。

## :memo: leetcode solution
* :medal: **思考一**: 我第一次的想法就是 backtracking，但一定會超時，這題我直接看答案解法怎麼思考的，所以他的解跟 55 類似，greedy，核心思想是你要怎麼選下一步，走的下一步可以讓你走下下一步可以到最遠的。
* 用下圖來說明，我們用 **nums = [2,3,1,1,4]** 來當例子。
* **第一步**一定是走到 index = 0 的這個位置，然後下一步可以選擇的是要**走一步(藍色)**，還是**走兩步（紅色）**，那呼應到我們思考一所講的，我們要走下一步是要考量到我們走得下一步是不是可以讓下下一步走最更遠，
* 那從圖中可以看到藍色的是可以讓我們走最遠的，因此在這個階段我們選擇走一步，然後就一直走到 list 的尾端，當然要計算走的步數。


## :memo: leetcode solution code

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 一開始的位置是在 index = 0
        cur = 0
        # 步數
        count = 0
        
        while cur < len(nums) - 1:
        
            # 下一步可以走的步數範圍
            start = cur + 1
            end = cur + nums[cur]
            
            # 當可以走的步數超過 nums ， 就代表我只要再 run 一次，我就可以走到底了
            if end >= len(nums) - 1:
                count += 1
                break
            
            # 找出下一步的下一步最遠的
            maxfar = 0
            next_step = 0
            while start <= end:    
                if start + nums[start] > maxfar:
                    maxfar = start + nums[start]
                    next_step = start
                
                start += 1
            
            cur += next_step - cur
            count += 1
            
        return count

## :memo: BigO
* 時間複雜度: O(len(nums)^2)，最差的狀況。
* 空間複雜度: O(1)

## :memo: better solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        jumps = 0
        current_jump_end = 0
        farthest = 0
        
        for i in range(len(nums) - 1):
            # we continuously find the how far we can reach in the current jump
            farthest = max(farthest, i + nums[i])
            # if we have come to the end of the current jump,
            # we need to make another jump
            if i == current_jump_end:
                jumps += 1
                current_jump_end = farthest
        return jumps

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