^ cout<< no_of_steps[arr_length -1];
On Mon, Jul 9, 2012 at 8:44 PM, algo bard <[email protected]> wrote:
> 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.
