This can be solved using Dynamic Programming approach. Let MinJump(n) = Minimum number of Jumps required to reach the Nth index of array A.
then, for 1< i < N, MinJump(i) = Min{1 + MinJump(j)} for all j such that (0<= j < i) and (j + A[j] >= i). We can prepare an auxiliary array say MinJump[1..N] where for MinJump[i] contains the minimum jump required to reach ith index of array A and use MinJump[1...i] and A[1....i] to calculate the value of A[i+1] and so on.. HTH, Sumit On Mon, Jul 9, 2012 at 7:02 PM, Akshat Sapra <sapraaks...@gmail.com> wrote: > Given an array A and the elements stored in an array denotes how much jump > an element can make from that array position. For example there is an array > A = {4 0 0 3 6 5 4 7 1 0 1 2} > > Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You > are stuck if you end up at 0. > You have to output the minimum number of jumps that can be made from > starting position to end position of an array. > > -- > > > Akshat Sapra > Under Graduation(B.Tech) > IIIT-Allahabad(Amethi Campus) > *--------------------------------------* > sapraaks...@gmail.com > akshatsapr...@gmail.com > rit20009008@ <rit20009...@gmail.com>iiita.ac.in > > -- > 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. > -- 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.