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
This solution timed out.
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