# 【LeetCode】 45. Jump Game II

## Description
> Given an array of non-negative integers, 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.

> 給一非負整數陣列，你一開始在陣列起始的位置。
> 陣列中的每個元素，代表你在這一格最遠可以跳多遠。
> 你的目標是跳到陣列的最後一格，請找出你最少只需要跳幾次。

## Example:

Example:

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

## Solution

* 使用**貪婪法**，只在乎當下最遠可以到哪裡。
* 去紀錄、計算當下最遠可以到哪裡，如果你可以到第`i`格，代表你有能力可以到`0~i`的任何一格。
* 如果你已經在第`i`格，你下次就可以到`i+nums[i]`格。利用這點去不停更新最遠距離。
* 記住，不要去重複的格子試圖更新最遠距離，因為每一格提供給你的距離是固定的，因此計算過的格子就應該跳過。
* 我下面的code利用`last`去紀錄上一次更新到哪裡。

### Code

class Solution {
public:
    int jump(vector<int>& nums) {
        int step=0;
        int count=0;
        int next=0;
        int last=0;
        for(;step<nums.size()-1;count++)
        {
            for(int i=last;i<=step;i++)
            {
                if(i+nums[i]>next)
                {
                    next=i+nums[i];
                }
            }
            last=step;
            step=next;
        }
        return count;
    }
};

###### tags: `LeetCode` `C++`