# Leetcode 45. Jump Game II
###### tags: `leetcode` `daily` `greedy`

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

# Method Greedy
:::info
:bulb: **作法講解**:
concept:
initialize, position = 0, we can jump into 1 ~ nums[0],
then we can choose best solution in 1 ~ nums[0],
best solution is where we can jump next position.

we can choose best position and jump until reach the position n-1.

step 1, use 2 variable last means this run last position.
next_pos means this run best solution.

step 2, we can choose best solution(next_pos) until we reach last position (last).
when we reach last,
update last to next_pos,

step 3, repeats step 2, until last is bigger and equal than (n-1).
:::

TC: O(N) SC: O(1)
:::spoiler 完整程式碼

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

:::