DP Jump Game¶
Table of Contents¶
- 1306. Jump Game III (Medium)
- 2770. Maximum Number of Jumps to Reach the Last Index (Medium)
- 403. Frog Jump (Hard)
- 1340. Jump Game V (Hard)
- 1871. Jump Game VII (Medium)
- 1696. Jump Game VI (Medium)
- 975. Odd Even Jump (Hard)
- 1654. Minimum Jumps to Reach Home (Medium)
- 656. Coin Path (Hard) 👑
- 2297. Jump Game VIII (Medium) 👑
1306. Jump Game III¶
from collections import deque
from typing import List
# BFS
def canReach(arr: List[int], start: int) -> bool:
n = len(arr)
visited = [False for _ in range(n)]
q = deque([start])
while q:
i = q.popleft()
if arr[i] == 0:
return True
visited[i] = True
for j in [i - arr[i], i + arr[i]]:
if j in range(n) and not visited[j]:
q.append(j)
return False
arr = [4, 2, 3, 0, 3, 1, 2]
start = 5
print(canReach(arr, start)) # True