## Minimum number of jumps to reach end

#include <iostream> #include <climits> int minJumps(int arr[], int n) { int *jumps = new int[n]; if(n==0 || arr[0]==0) return 0; jumps[0] = 0; for(int i=1; i<n; i++) { jumps[i] = INT_MAX; for(int j=0; j<i; j++) { if(i<=j+arr[j] && jumps[j]!=INT_MAX) { jumps[i] = jumps[j] + 1; break; } } } return jumps[n-1]; } int main() { int arr[] = {1,2,3,4,5}; int n = sizeof(arr)/sizeof(arr[0]); std::cout<<"Minimum number of jumps to reach end is "<<minJumps(arr, n); return 0; }

Advertisements