Q. Minimum Number of Jumps to reach out of Array starting from first element

Here  at  position  a[i]  we  can  jump  from  a[i]  to  a[i+a[i]]  positions

INPUT:  {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};

OUTPUT:  2  i.e  1->3->9

METHOD  1  DP

DP  can  be  used  as  reaching  i  th  index  we  require

 a[i]=a[j]+j  where  j <= i

so  dp[i]=dp[j]+1;  where  i th  index  stores number  of  jumps  to  reach  a[i]

#include<stdio.h>
int max(int* dp,int n)
{
int max=0;
for(int i=0;i<n;i++)
if(dp[i]>max)
max=dp[i];
return max;
}
int main()
{
int n=11;
int arr[11]={1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int dp[11]={0,0,0,0,0,0,0,0,0,0,0};
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(i==j+arr[j])
{dp[i]=dp[j]+1;break;} }
}
if(dp[n-1]!=0)
printf("%d",dp[n-1]);
else
{
printf("%d",max(dp,n)); }
}

Time  =O(n^2)
Space=O(n)  for  dp  array

METHOD  2  GREEDY

Here  we  can  also  use  greedy  approach  as  we  can  see  we  may  choose  max{j+a[j]}  as  our  next  move  i.e  we  can  reach  destination  as  easy  as  possible

#include<stdio.h>
int max(int* arr,int low, int high)
{
printf("%d   %d\n",low,high);
int max=0;
for(int i=low;i<=high;i++)
if(i+arr[i]>max)
max=arr[i]+i;
return max;
}
int main()
{
int n=11;
int arr[11]={1, 1, 2, 5, 1, 2, 2, 1, 1, 8, 9};
int jump=0;
for(int i=0;i<n;)
{
//printf("%d\t",i);
i=max(arr,i+1,i+arr[i]);
jump++;
if(i>11)
break;
}
printf("%d",jump+1);
}

Time=  O(n)

Please  suggest  any  updates.........