int A[100];
int dist[100];
int N;
void findDist(int p, int d)
{
if (d < dist[p])
{
dist[p] = d;
for(int i = 0; i < p; ++i)
if ((i+A[i]) >= p)
findDist(i,d+1);
}
}
int main(int argc, char* argv[])
{
int i;
int location = 0;
printf("Number of elements:");
scanf("%d", &N);
for(i = 0; i < N; ++i)
{
printf("Element %d:", i);
scanf("%d",&A[i]);
}
for(i = 0; i < N; ++i)
dist[i] = N;
findDist(N-1, 0);
for(i = 1; i < N; ++i)
if (dist[i] == (dist[location]-1))
{
printf("Move %d to location %d\n", i-location, i);
location = i;
}
return 0;
}
On Aug 11, 3:07 am, Algo Lover <[email protected]> wrote:
> Given an array, start from the first element and reach the last by
> jumping. The jump length can be at most the value at the current
> position in the array. Optimum result is when you reach the goal in
> minimum number of jumps.
>
> For ex:
> Given array A = {2,3,1,1,4}
> possible ways to reach the end (index list)
> i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
> 4)
> ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
>
> Since second solution has only 2 jumps it is the optimum result.
>
> My solution is for any index i loop from i to i + A[i]
> find an index j where
> (j + A[j]) is maximum for all j.
> make i=j;
>
> This solution in O(n) i suppose coz we are picking each element twice
> in the worst case.
>
> I have read a O(n^2) DP solution for this problem.....Is there any
> case where my approach will fail ?
--
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.
