Yes, greedy algo doesn't work.. U shud hv DP.. plz post the soln which u
read..
A={2,2,3,4,1,1,1,1,1}
Ur algo gives 0,2,5,6,7,8(these are indices... index starts frm 0)
best soln is 0,1,3,7,8..
On Thu, Aug 11, 2011 at 2:37 PM, Arun Vishwanathan
<aaron.nar...@gmail.com>wrote:
> 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 <algolear...@gmail.com>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 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.
>>
>>
>
>
> --
> "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 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.
>
--
D.Tharun| Computer Science and Engineering, IIT Bombay | tharu...@iitb.ac.in |
+918097345806
--
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.
