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.