I think your recursive formula is wrong . This should be the actual
recursive formula .
Let dp[i] = minimum number of elements selected to reach i_th index .
Then dp[i] = min(dp[j])+1 , where j<i and j+a[j]>=i . I have tried
this code and works fine according to me.
int Jumps(int a[],const int n)
{
int dp[n],i,j,min;
for(i=0;i<n;i++)
dp[i] = 0;
dp[0] = 1; // One element is selected to reach 0th index
for(i=1;i<n;i++)
{
min = INT_MAX;
for(j=0;j<i;j++)
{
if((j+a[j]>=i)&&(min>dp[j]))
min = dp[j];
}
dp[i] = min+1;
}
return dp[n-1];
}
--
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.
