Ronzii's Blog

Just your average geek's blog

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;
}

March 16, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment