###### tags: `Leetcode` `medium` `greedy` `python` `Top 100 Liked Questions`

# 45. Jump Game II

## [題目連結:] https://leetcode.com/problems/jump-game-ii/

## 題目:
Given an array of non-negative integers ```nums```, you are initially positioned at the first index of the array.

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

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

**Example 1:**

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Example 2:**

Input: nums = [2,3,0,1,4]
Output: 2

## 解題想法:
兄弟題目: [55. Jump Game](/YoXJ8azhSSmZ6BRrdwPgCw)
* nums[i]表示該位子可以一次往後跳多少格(1~nums[i]格)

* 求最少步能達到尾
* 想法:
* pre_pos:紀錄上一次跳可以跳到最遠的位置
* far_pos:紀錄計算本次可以跳到最遠的位置
* 逐一更新每次當前可以跳到最遠的點
* 若遍歷到pre_pos的位置了
* 總步數+1
* 更新pre_pos為far_pos

* 示意圖:

nums[0]第一次跳可以跳到i=2
我們可以由nums[0]~nums[2]中選擇其中可以跳到最遠位置的點
例如nums[1]=3 可以跳到位置i=4
則第二跳選擇中:
使用i=2此位置與i=4位置-> nums[2]~nums[4]中選擇可以跳到最遠的位置點
以此類推:")

nums=[2, 3, 1, 1, 4]
i    nums[i]   steps  pre_pos far_pos
0      2         1       2      2
1      3         1       2      4
2      1         2       4      4
3      1         2       4      4

## Python:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #use greedy、bfs
        #time:O(n) space:O(1)
        steps=0
        #上一次跳可以跳到最遠的位置
        pre_pos = 0
        #far:計算本次可以跳到最遠的位置
        far_pos = 0
        for i in range(len(nums)-1):
            #每次更新當前可以跳到最遠的點
            far_pos=max(far_pos,i+nums[i])
            #若已經遍歷到上次能跳到的最遠位置
            if pre_pos==i:
                #進行下一次跳
                steps+=1
                pre_pos=far_pos
        return steps

ans = Solution()
print(ans.jump(nums=[2,3,1,1,4]))