---
# System prepended metadata

title: Leetcode 45. Jump Game II
tags: [greedy, daily, leetcode]

---

# 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 完整程式碼
```cpp=
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;
    }
};
```
:::


