403. Can You Reach the End
Each position holds the MAXIMUM number of steps you may jump forward from it.
You start at position 0. Print yes if the last position can be reached and
no otherwise.
2 3 1 1 4 -> yes jump 1 to index 1, then 3 to the end
3 2 1 0 4 -> no every route stops at the 0
The value at a position is a limit, not a requirement: from a 3 you may jump 1, 2 or 3.
The reachability table is the honest first solution:
reach[0] = true
reach[i + k] = true for every reachable i and every k in 1..a[i]
which is O(n^2) and completely correct.
Watching what that table actually contains suggests something better. Every
reachable position forms one unbroken prefix, because if position i is
reachable then so is everything between it and where it can jump. So the whole
table collapses to a single number: the furthest index reachable so far.
for i in 0..n-1:
if i > furthest: answer is no, the run is broken
furthest = max(furthest, i + a[i])
One pass, no array. That collapse from a table to a single value is the move worth learning, and it recurs whenever the DP state turns out to be an interval rather than a set.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 100000`
Input
The first line contains an integer n.
The second line contains n space-separated non-negative integers, the maximum jump from each position.
Output
Print yes if the last position is reachable from position 0, or no otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.