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.