**Jump Game cpp**

**Jump Game cpp**

**Given an array of non-negative integers, you are initially positioned at the first index of the array.**

**Each element in the array represents your maximum jump length at that position.**

**Your goal is to reach the last index in the minimum number of jumps.**

**For example:**

**Given array A = [2,3,1,1,4]**

**The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.**

int jump(int A[], int n) {

int *c = new int[n];

fill(c, c + n, n);

c[0]=0;

bool breakExtLoop=false;

for (int i =0 ; i < n ; i++)

{

if(breakExtLoop)

break;

for(int j=1;j<=A[i] && (i+j)< n;j++)

{

if(c[i+j] > c[i]+1)

c[i+j]=c[i]+1;

if((i+j)==n-1)

{

breakExtLoop=true;

break;

}

}

}

return c[n-1];

}

**An alternative to above solution that runs fast:**

*int jump(int A[], int n) {*

*int canArrive = 0, res = 0, lastCanArrive = 0;*

* for(int i = 0; i < n; i++)*

* {*

* if(i > lastCanArrive)*

* {*

* res++;*

* lastCanArrive = canArrive;*

* if(lastCanArrive >= n-1)*

* break;*

* }*

* if(i + A[i] > canArrive)*

* canArrive = i + A[i];*

* }*

* return res;*

* }*