Given an array with each element storing the maximum steps an element can take toward the end of the array. Can we start at 0 and reach len(A) – 1? \

# 1D Dynamic programming

We define D, a 1D dynamic table. D[i] stores if we can reach the end starting at [i].

This problem has optimal solution: The solution to D[i] can be found by checking if D[i + A[i]] == True.

The result will be at D[0]

This solution timed out.

# Greedy

We observe that we don’t necessary need to keep the table since we are not reconstructing the solution. Further more, we only need to know if our element at i can reach the last element ahead of i that could reach the end.

last_possible_elem_pos = len(nums) - 1
for i in range(len(nums) - 1, -1, -1):
if i + nums[i] >= last_possible_elem:
last_possible_elem = i
return last_possible_elem == 0