At each location if the value is k , find the largest value in the next k elements and jump there.
This greedy approach works in 0(n^2) and i believe it works. If not can someone give me a counter example ? On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu <[email protected]> wrote: > @jammy Even I felt the same, but the greedy 'algo' u suggest is actually > IMHO not a greedy approach. You just take each arr[i] and jump *without > deciding a locally optimal policy* . SO, if u were to *see* arr[i] and > *decide* on the optimal policy I feel one would follow d same steps as in a > DP solution. Its only just that the implementation would be O(n^2). Just to > add, this is the greedy approach I feel: > > greedy_min_steps[n] > for i = 0; i < n; i++: > for (j = 0; j < input[i]; j++) > greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ], > greedy_min_steps[ i ] + 1) > > this is the greedy approach I build and I see this being exactly similar to > my DP approach. There are instances of greedy approach based algorithms > which have *optimized* DP counter parts. I feel this problem is one of them. > More ideas ? > > > > > Programmers should realize their critical importance and responsibility in > a world gone digital. They are in many ways similar to the priests and monks > of Europe's Dark Ages; they are the only ones with the training and insight > to read and interpret the "scripture" of this age. > > > On Sat, Jan 15, 2011 at 2:14 AM, Jammy <[email protected]> wrote: > >> @Avi Greedy approach doesn't work since you can't ensure the choice is >> locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give >> you 3,1,8,3 while otherwise DP would give you 3,9,3. >> >> On Jan 14, 6:11 am, Avi Dullu <[email protected]> wrote: >> > I guess u got confused with the comment I wrote, I have added 2 print >> > statements and now I guess it should be clear to you as to why the code >> is >> > O(n). The comment means that each element of the min_steps_dp will be >> > ACCESSED only ONCE over the execution of the entire program. Hence the >> outer >> > loop still remains O(n). The next_vacat variable if u notice is always >> > incremental, never reset to a previous value. >> > >> > #include<stdio.h> >> > #include<stdlib.h> >> > >> > #define MAX 0x7fffffff >> > >> > inline int min(int a, int b) { >> > return a >= b ? b : a; >> > >> > } >> > >> > int find_min_steps(int const * const input, const int n) { >> > int min_steps_dp[n], i, temp, next_vacant; >> > for (i = 0; i < n; min_steps_dp[i++] = MAX); >> > >> > min_steps_dp[0] = 0; >> > next_vacant = 1; // Is the index in the array whose min_steps needs to >> be >> > updated >> > // in the next iteration. >> > for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) { >> > temp = i + input[i]; >> > if (temp >= n) { >> > min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + >> 1); >> > temp = n - 1; >> > } else { >> > printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] >> + >> > 1); >> > min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1); >> > } >> > if (temp > next_vacant) { >> > printf("i: %d \n", i); >> > for (; next_vacant < temp; next_vacant++) { >> > printf("next_vacant: %d \n", next_vacant); >> > min_steps_dp[next_vacant] >> > = min(min_steps_dp[temp], min_steps_dp[next_vacant]); >> > } >> > } >> > } >> > for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n"); >> > return min_steps_dp[n-1]; >> > >> > } >> > >> > int main() { >> > int n, *input, i; >> > scanf("%d",&n); >> > if ((input = (int *)malloc(n * sizeof(int))) == NULL) { >> > return -1; >> > } >> > for (i = 0;i < n; scanf("%d",&input[i++])); >> > printf("Minimum steps: %d\n",find_min_steps(input, n)); >> > return 0; >> > >> > } >> > >> > Programmers should realize their critical importance and responsibility >> in a >> > world gone digital. They are in many ways similar to the priests and >> monks >> > of Europe's Dark Ages; they are the only ones with the training and >> insight >> > to read and interpret the "scripture" of this age. >> > >> > On Fri, Jan 14, 2011 at 1:49 PM, Decipher <[email protected]> >> wrote: >> > > I don't think the inner loop is executing only once . Kindly check it >> for >> > > this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner >> loop >> > > you will find that for same values of i(Outer index) inner loop is >> called. >> > > Its an O(n2) solution . >> > >> > > -- >> > > 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]<algogeeks%[email protected]> >> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[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]<algogeeks%[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.
