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 <[email protected]> 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)
> *--------------------------------------*
> [email protected]
> [email protected]
> rit20009008@ <[email protected]>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 [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.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
