Jump Games
55. Jump Game
1 min readApr 7, 2020
DP TLE
The following DP should have a time complexity of O(n²), however, it got TLE.
74 / 75 test cases passed. TLE.
from functools import lru_cache
class Solution:
def canJump(self, A: List[int]) -> bool:
N = len(A)
print(N)
@lru_cache(None)
def dp(i):
if i==N-1:return True
if A[i]==0:return False
if i+A[i]>=N-1:return True
return any(dp(i+k) for k in range(1, min(A[i]+1,N)))
return dp(0)Greedy works
The solution is modified from here by Stefan.
class Solution:
def canJump(self, A: List[int]) -> bool:
max_reach = 0
for i, a in enumerate(A):
if i>max_reach:return False
max_reach = max(max_reach, i+a)
return TrueRelated problems
In order to fully understand this kind of question, I strongly recommend the read also solve problems mentioned in the following article.
