/*
**
** Jump() using greedy algorithm, the run time is O(n)
** jump() usine dynamic programming to solve, the run time is O(n^2)
**
*/


int Jump(int A[], int n) 
{
    int k = 0; //the position from where we could jump the furtheset so far 
    int s = 0; //steps to jump
	int j = 0; //the last furthest position we checked
	int i = j+1; //the index that begin to be checked
	
    while(i < n)
    {   
        i = j+1;			//the ranges that we need to check with
		int f =  k + A[k];	//furthest we could jump so far
		j = f;	//save it as the end where we stop to check
		//we only need to check from the position we checked last time to the furthest position
        for (; i <= j && i < n; ++i)
                if (f <= (A[i]+i)) k = i , f = A[i]+i; //update the new furthest
		
        ++s; 
    }
    
    return s; 
}

int jump(int A[], int n) 
{
    if (n < 1)return 0;

    int steps[n];
    steps[n-1] = 0; //init last step as 0
    //calculate for each elemnt
    for (int i = n-2; i >=0; --i)
    {
        int step = n;//the max step would not larger than the length of array.
        for (int j = 1; j <= A[i] && (i+j) < n; ++j)
            if (step > steps[i+j]) step = steps[i+j];

        steps[i] = step + 1;
    }

    return steps[0];
}

#include<stdio.h>
int main(int argc, char** argv)
{
    int A[] = {2,3,1,1,4};
    int B[] = {100,99,98,97,96,95,94,93,92,91
            ,90,89,88,87,86,85,84,83,82,81
            ,80,79,78,77,76,75,74,73,72,71
            ,70,69,68,67,66,65,64,63,62,61
            ,60,59,58,57,56,55,54,53,52,51
            ,50,49,48,47,46,45,44,43,42,41
            ,40,39,38,37,36,35,34,33,32,31
            ,30,29,28,27,26,25,24,23,22,21
            ,20,19,18,17,16,15,14,13,12,11
            ,10,9,8,7,6,5,4,3,2,1,1,0};
            
    printf("Greedy :%d\n", Jump(A,5));
    printf("Dynamic:%d\n", jump(A,5));
    printf("Greedy :%d\n", Jump(B,sizeof(B)/4));
    printf("Dynamic:%d\n", jump(B,sizeof(B)/4));
    return 0;
}