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 [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.
