LeetCode: Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Using Greedy Algorithm

bool canJump(int A[], int n) {

if (0 == n)

            return false;

        int cur_max = A[0];

        int i = 0;

        while (i <= cur_max) {

            cur_max = max(cur_max, i + A[i]);

            

            if(cur_max >= n - 1)

                return true;

                

            ++i;

        }

        return false;

    }

bool canJump(int A[], int n) {       

        if (1 == n)

            return true;

        int i = 0;

        while (i < n)

        {

            int currMax = A[i] + i;

            

            if (0 == A[i])

                return false;

            if (currMax >= n - 1)

                return true;

                

            int tmpMax = 0;

            for (int j = i + 1; j <= currMax; ++j)

            {

                if (A[j] + j > tmpMax)

                {

                    tmpMax = A[j] + j;

                    i = j;

                }

            }

        }

        

        return (i >= n - 1);

    }

DP
bool canJump(int A[], int n) {
        bool ATag[n];
        for (int i = n - 1; i >= 0; --i)
        {
            ATag[i] = false;
            int maxReach = A[i] + i;
           
            if (maxReach >= n - 1)
            {
                ATag[i] = true;
                continue;
            }
           
            for (int j = maxReach; j > i; --j)
            {
                if (ATag[j])
                {
                    ATag[i] = true;
                    break;
                }
            }
        }
        return ATag[0];
    }
Read full article from Jump Game