int no_of_steps[arr_length] = {MAX};
if ( (arr_length==0) || (arr[0] == 0) ) //if there are no elements or
the very first element is 0 -> we can't jump anywhere
return MAX;
no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.
for (int i=1; i<arr_length; i++)
{
no_of_steps [i] = MAX;
for(int j=0; j<i; j++) //from 0th element till the element we need
to jump to.
{
if( arr[j] >= (i - j) ) //if it is possible for us to jump from
jth element to ith element.
{
if( no_of_steps[i] > no_of_steps[j] + 1) // if no. of steps to
reach the ith element recorded till now is greater than the no of
{ //
steps reqd to reach jth element + 1, then replace.
no_of_steps[i] > no_of_steps[j] + 1;
}
}
}
}
cout<<no_of_steps[n-1];
On Mon, Jul 9, 2012 at 8:32 PM, Mr.B <[email protected]> wrote:
> There is a greedy solution discussion about this approach. I don't have a
> formal proof for this.
> Any counter example will be helpful.
>
> at every place 'k' .. do the following.
>
> --> find max ( a[k+i]+i ) where 1 <= i <= a[i]
>
> for the given example:
> A = {4 0 0 3 6 5 4 7 1 0 1 2}
>
> initially a 4, the loop will be.
> 0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
> now at 6. (since, you can't reach end.)
> 5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, ==> 10 is max. jump to 7.
> make another step. (but you can reach the end.) so jump to last.
>
> this is greedy approach.. and a linear time soultion.
>
>
> On Monday, 9 July 2012 09:32:08 UTC-4, Akshat 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 view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
>
> 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.
