# 45-Jump game II
###### tags: `Medium`
* Question:
https://leetcode.com/problems/jump-game-ii/
* Key:
1. DP:
從第一步開始會影響下一步，所以使用DP，藉由設定maxPos和end兩變數，來記錄最大距離和最遠結束位置，每次迭代會更新maxPos，end只有在到達最遠結束位置時更新，更新值為maxPos。
因為過程中小的元素距離短加上走一次就算一步並且會累積前面步數，因此只在乎最小步數且一定會到達終點的條件下，每次更新最遠結束位置已是最小步數了，只要盡可能把距離拉遠，到達該結束位置時，再更新步數即可

class Solution {
public:
int jump(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;

    int ans = 0;
    int end = 0;
    int maxPos = 0;
    for(int i = 0; i < n - 1; i++){
        maxPos = max(maxPos, nums[i] + i);
        if(i == end){
            end = maxPos;
            ans++;
        }
    }

    return ans;
}
};