@shashank acc to me the problem can be done easily using greedy approach https://ideone.com/dYbUd ( it is your non optimal greedy solution with just one line added ) couldn't find any case where the above code is giving wrong answer .
if you know any case, please let me know. I wrote a dp O(n^2) solution before that but found that same can be done using greedy as well On Fri, Aug 12, 2011 at 7:57 PM, WgpShashank <shashank7andr...@gmail.com> wrote: > A Top Down Memoization DP Algorithm Will be As Follow > > Step 1. Declare an array of size N say jump[N]; > where ith position indicates the number of jumps requires to reach from > start to this (ith) position in array . > > Step 2. Initialize jump[0]=0; indicates to reach oth location form starting > location (3which is obviuosly 0) we don't requires any jump. > > Step 3. Check size of array and value at 0th location in array For first > index, optimum number of jumps will be zero. Please note that if value at > first index is zero, we can’t jump to any element and return infinite.so > these tow cases are > A.If size of array==0 means array is of zero size; > B.If value at zero then we can't jump or we can't proceed > to next location > > Step 4. Run Through Loop for remaining elements in array and Initialize > jump[i] as infinite. where > 1<=i<=N. > Sub-step 4A. (Please Note j runs in inner loop until i<=j+a[j] ) > if jump[i]<jump[j]+1 update jump[i] & repeat until j>i (this > whole processing will happen in > inner loop). e.g. for each ith element this loop will run & > tries to figure out optimal/minimum > number of jumps required to reach this ith position from starting > of array . > > Step 5. After running above algorithm we will return array[n-1] that will > show number of jumps required > to reach last elemnt in array from start. > > Time Complexity O(N^2) > Space Complexity O(N) > Hope You Can Convert it into Production Code > > Do Notify me via mail if i missed anything ?? > > Regards > Shashank Mani "Computer Science Is Awesome So Why I Write Code" > Computer Science > Birla institute of Technology Mesra > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/37L_lAEKGVkJ. > 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. > -- Rohit Jangid Under Graduate Student, Deptt. of Computer Engineering NSIT, Delhi University, India -- 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.
