# 55. 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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

# Solution

Approach 1: Backtracking.

Approach 2: DP top-down. For each index, mark all indices it can reach as true -- O(N^2).

Approach 3: DP bottom-up.

Approach 4: Greedy. Find the farthest index by iterating through each index -- O(N).

# Code (Python)

Approach 2:

    def canJump(self, nums: List[int]) -> bool:
        # idea: for each index, mark all indices it can reach as true -- O(N^2)
        can_reach = [True] + [False for _ in range(1, len(nums))]
        for i in range(len(nums) - 1):
            if can_reach[i]:
                for j in range(i + 1, min(i + nums[i] + 1, len(nums))):
                    can_reach[j] = True
                if can_reach[-1]:
                    return True
        return False

Approach 4:

    def canJump(self, nums: List[int]) -> bool:
        # idea: greedy. Find the farthest index by iterating through each index -- O(N).
        farthest = 0
        for i in range(len(nums)):
            if i <= farthest:
                farthest = max(farthest, i + nums[i])
                if farthest >= len(nums) - 1:
                    return True
        return False

# Code (C++)

Approach 1:

// Backtracking (Time Limit Exceeded).
class Solution {
private:
    bool canJump(vector<int>& nums, int head) {
        if (head == nums.size() - 1)
            return true;
        for (int i = 1; i <= nums[head]; ++i)
        {
            if (head + i < nums.size() && canJump(nums, head + i))
                return true;
        }
        return false;
    }
public:
    bool canJump(vector<int>& nums) {
        return canJump(nums, 0);
    }
};

Approach 2:

// DP top-down.
class Solution {
private:
    vector<int> memo;
    bool canJump(vector<int>& nums, int head) {
        if (memo[head] >= 0)
            return memo[head];
        for (int i = 1; i <= nums[head]; ++i)
        {
            if (head + i < nums.size() && canJump(nums, head + i))
            {
                memo[head] = 1;
                return true;
            }
        }
        memo[head] = 0;
        return false;
    }
public:
    bool canJump(vector<int>& nums) {
        memo = vector<int>(nums.size(), -1);
        memo[nums.size() - 1] = 1;
        return canJump(nums, 0);
    }
};

Approach 3:

// DP bottom-up.
class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool memo[nums.size()] = {false};
        memo[nums.size() - 1] = true;
        for (int i = nums.size() - 2; i >= 0; --i)
        {
            int furthestJump = std::min(i + nums[i], (int)nums.size() - 1);
            for (int j = i + 1; j <= furthestJump; ++j)
            {
                if (memo[j])
                {
                    memo[i] = true;
                    break;
                }
            }
        }
        return memo[0];
    }
};

Approach 4:

// Greedy.
class Solution {
public:
    bool canJump(vector<int>& nums) {
        // From right to left (also the optimization of DP top-down).
        int prevGoodPos = nums.size() - 1;
        for (int i = nums.size() - 2; i >= 0; --i)
        {
            if (i + nums[i] >= prevGoodPos)
                prevGoodPos = i;
        }
        return prevGoodPos == 0;

/*
        // From left to right.
        int furthestJump = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i > furthestJump)
                return false;
            furthestJump = std::max(furthestJump, i + nums[i]);
            if (furthestJump >= nums.size() - 1)
                return true;
        }
        return true;
*/
    }
};