###### tags: `LeetCode` `Medium`
# LeetCode #45 [Jump Game II](https://leetcode.com/problems/jump-game-ii)
### (Medium)
給你一個非負整數數組 nums ，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
假設你總是可以到達數組的最後一個位置。

---
設定start(每次檢查開始點), end(每次檢查結束點), maxend(每次檢查能達到最遠點), step(總步數)。

設一while迴圈while(end<nums.size()-1), 首先每次迴圈開始時先將step加一, 而由於題目前提說"總是可以達到數組的最後一個位置", 故可先將maxend設為end+1(最差也能多走一步)。

接下來執行本輪檢查, 由start檢查到end, 途中更新maxend為現在maxend與i+nums[i](也就是該點加上該點能跳躍的距離)中取較大值, 而在檢查途中若i+nums[i]≥nums.size()-1則代表在該點可以直接跳到終點, 此時直接回傳step。檢查結束後, maxend的值代表了在這輪(起始點start到結束點end)中可以達到的最大距離。於是開始新一輪的檢查, 此時start為舊的end+1, end為舊的maxend, maxend為新的end+1(也就是說檢查新一輪是否有某個點能超過舊的maxend, 而再不濟也是舊的maxend+1)。

如此持續直到end≥nums.size()-1, 然後回傳step值。

---

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        int start=0;
        int end=0;
        int step=0;
        while(end<n-1){
            step++;
            int maxend=end+1;
            for(int i=start;i<=end;i++){
                if(i+nums[i]>=n-1)return step;
                maxend=max(maxend, i+nums[i]);
            }
            start=end+1;
            end=maxend;
        }
        return step;
    }
};