My solution is based on the observation that if you can reach index `i`

, then you are always able to reach index `i - 1`

too (**proof:** think of the last jump taken to reach index `i`

. If it was of length `1`

, then you were already at index `i - 1`

. If it was of length `>= 2`

, then you could have taken a 1-unit smaller jump to land on `i -1`

instead of `i`

). Furthermore, following the same reasoning, if you can reach index `i`

in `w`

jumps, you can also reach index `i-1`

using no more than `w`

jumps (but perhaps even less).

Let `reach[i]`

be the farthest you can reach in the next jump assuming you are able to reach index `i`

. (Remember, if you can reach in `i`

in `w`

jumps, then you can also reach any smaller index in no more than `w`

jumps). Therefore, `reach[i]`

is simply `max(k + nums[k])`

for all `k`

with `0 <= k <= i`

).

You can precompute `reach[i]`

in O(n) for all `i`

's. (Note that in my code I reuse `nums`

to precompute it and avoid defining a new array to save some memory.)

After that you just simulate the jumps, always reaching as far as you can until you reach the end.

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