Minimum number of jumps to reach end of the array(By DP)

#include<bits/stdc++.h>
using namespace std;
int minimumjump(int a[], int n)
{
    int jump[n], i, j;

    if(n == 0 || a[0] == 0)
        return INT_MAX;

    jump[0] = 0;

    for(i=1;i<n;i++)
    {
        jump[i] = INT_MAX;
        for(j=0;j<i;j++)
        {
            if(j+a[j] >= i && jump[j] != INT_MAX)
            {
                jump[i] = min(jump[i], jump[j]+1);
                break;
            }
        }
    }

    return jump[n-1];
}
int main()
{
    int n, i;

    cout << "Enter Array Size :: ";
    cin >> n;

    int a[n];

    cout << "\nEnter Each Array Element :: \n";
    for(i=0;i<n;i++)
    {
        cin >> a[i];
    }

    int p = minimumjump(a, n);

    cout << "Minimum Jumps Required For Reach End of The Array :: " << p << "\n";

    return 0;
}

Comments