Skip to content

DP Jump Game

Table of Contents

1306. Jump Game III

1306. Jump Game III - Python Solution
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

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, dynamic programming, sliding window, prefix sum

1696. Jump Game VI

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, queue, heap priority queue, monotonic queue

975. Odd Even Jump

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, dynamic programming, stack, monotonic stack, ordered set

1654. Minimum Jumps to Reach Home

656. Coin Path

2297. Jump Game VIII

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, stack, graph, monotonic stack, shortest path

Comments