Recursion to build the jump tree

    def __init__(self):
        self.reached = False
    def canJump(self, nums: 'List[int]') -> 'bool':
        def recur_jump(nums, cur_pos):
            if cur_pos >= len(nums) - 1:
                self.reached = True
                return
            for i in range(1, nums[cur_pos] + 1):
                recur_jump(nums, cur_pos + i)

        if not nums:
            return True
        recur_jump(nums, 0)
        return self.reached

Time out since it will take a lot of time to populate the tree

Greedy

    def canJump(self, nums: 'List[int]') -> 'bool':
        if not nums:
            return True
        cur_pos = 0
        steps_avail = nums[cur_pos]
        while steps_avail > 0:
            cur_pos += 1
            steps_avail -= 1
            if cur_pos > len(nums) - 1:
                break
            if nums[cur_pos] > steps_avail:
                steps_avail = nums[cur_pos]

        return cur_pos >= len(nums) - 1

DP?

I didn’t think about this by myself. I saw it on the leetcode website.
We use a 1-d boo array to record if we can reach the end from position i.
For the last index, it is always true. Then we traverse back.

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

        return DP[0];
    }

In each outer loop, we try to check if we can reach to the end from i.
In each inner loop, we start from i + 1 till the furthest place we can go( i + nums[i]). If we find any DP[j] == True, that means we can jump from i to j, and j can jump to end.