Algo Notes: Jump Game 2

Description of problem here

The first impression is that prehaps the best jump to make is one that'll allow for most jump length since this step will lead to least total jumps because the further we can move from a given step the better. Unfortunately this is not always true, since the step one can move farthest away from might not be the step one can move farthest down the array from. This is the difference between jump lenght and reach.

Imagine an array, [10,9,8,7,6,5,4,3,2,1,1,0], choosing the next step to be the one with the most jump length results in 10 jumps. If we consider the next best step (the greedy choice) to be the one with the most reach, however, results in 2 since the first jump will be the the penulatimate element with a reach of 11, and it's one step til the end (the only available step).

.back