@juver++ : what is the greedy approach one could take here? I know it would
be wrong, but I tried to come up with a test case for greedy failure, but
realized the greedy policy here will be equivalent to the dp.
@Decipher: your's seems to be a O(n^2) solution. Here in the O(n) version of
it.
#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 {
min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
}
if (temp > next_vacant) {
// this loop executes only ONCE for each element in the array, so over
the
// course of execution, is an O(n) loop only. The order of the outer
loop still
// remains O(n).
for (; next_vacant < temp; 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 Wed, Jan 12, 2011 at 11:27 PM, juver++ <[email protected]> wrote:
> No, there is a counterexample fot the greedy.
>
> --
> 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.
