>Given an array of integers of size N, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array starting from the first element. Please note that you need to land exactly on the end of the array and not after that point. Obviously you always have a strategy to reach the end in N moves by always avoiding to jump and deciding to move to the next position but N is not necessarily the minimum.
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3 with the sequence 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 (2+1 goes to 3 where you can jump to 5) or 8 (2+2 goes to 4 where you can jump to 8) or 9 (2+3 goes to 5 where you can jump to 9)
If an element is 0, then cannot make any jumps
There is a simple quadratic solution with Dynamic Programming, but I was not able to get any linear solution. Is it possible?