Description Link to heading

45.jump-game-ii

Solution Link to heading

In outer loop, we traverse from back to front, while in inner loop, we traverse from front to back, to find the station with minimum index that can arrive at destination. Make the station the new destination, and cnt++.

Code Link to heading 

#include <vector>
using std::vector;
class Solution {
  public:
    int jump(vector<int> &nums) {
        int cur_end = nums.size() - 1;
        int cnt = 0;
        while (cur_end != 0) {
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] + i >= cur_end) {
                    cur_end = i;
                    cnt++;
                    break;
                }
            }
        }
        return cnt;
    }
};