^ cout<< no_of_steps[arr_length -1]; On Mon, Jul 9, 2012 at 8:44 PM, algo bard <algo.b...@gmail.com> 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 <sravanreddy...@gmail.com> 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) >>> *--------------------------------------* >>> 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 view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ. >> >> 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.