Skip to content

DP Jump Game

Table of Contents

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

2770. Maximum Number of Jumps to Reach the Last Index

403. Frog Jump

1340. Jump Game V

1871. Jump Game VII

1696. Jump Game VI

975. Odd Even Jump

1654. Minimum Jumps to Reach Home

656. Coin Path

2297. Jump Game VIII

Comments