@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]> > > . > > 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.
