`/*`

` Algo:`

` Lets define a function called hop which is number of steps required to reach the end of array from the given position, So`

` hop(i) = INT_MAX if a[i] == 0`

` hop(i) = 1 + min(hop(j) where j is from i + 1 to i + a[i]`

` hop(0) is the required answer`

`*/`

#include <stdio.h>

#include <limits.h>

int minhops(int a[], int n) {

int hop[n] ;

int i = n;

while(i--) {

if(a[i] == 0)

hop[i] = INT_MAX;

else {

if(i + a[i] >= n)

hop[i] = 1;

else {

int j, min = INT_MAX;

for(j = i + a[i]; j > i; --j){

if(hop[j] < min)

min = hop[j];

}

hop[i] = min + 1;

}

}

}

return hop[0];

}

int main() {

int a[] = {1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};

int n = minhops(a, 11);

if(n != INT_MAX)

printf("%d\n", minhops(a, 11));

return 0;

}

Advertisements

This comment has been removed by the author.