I did not get the optimal solution part..how is that u jump 1 to index 1?
On Thu, Aug 11, 2011 at 10:07 AM, Algo Lover <[email protected]> wrote:
> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
"People often say that motivation doesn't last. Well, neither does bathing
- that's why we recommend it daily."
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
