Given an array, start from the first element and reach the last by
jumping. The jump length can be at most the value at the current
position in the array. Optimum result is when you reach the goal in
minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.
My solution is for any index i loop from i to i + A[i]
find an index j where
(j + A[j]) is maximum for all j.
make i=j;
This solution in O(n) i suppose coz we are picking each element twice
in the worst case.
I have read a O(n^2) DP solution for this problem.....Is there any
case where my approach will fail ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
