LeetCode 55 jump game

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

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax