Chương trình kiểm tra có thể vượt sông bằng đá lội trong Python

Cho danh sách vị trí đá stones (đã sắp xếp). Bắt đầu tại đá đầu, muốn đến đá cuối. Mỗi bước nhảy k-1, k, hoặc k+1 bước (k là độ dài nhảy trước). Kiểm tra có thể đến cuối không.

Ví dụ: stones = [0,1,3,4,5,6,8,9,13] → True (0→1→3→5→8→13).

Giải thuật (DFS + Memoization)

• Chuyển stones thành tập hợp stone_set để tra O(1).
• Hàm check(pos, prev_jump):
  • Nếu pos == end: True.
  • Thử nhảy prev-1, prev, prev+1 (nếu ≥1). Nếu vị trí mới có đá và check(next, jump) True → True.
• Gọi check(start, 0).

Mã nguồn Python

class Solution:
    def solve(self, A):
        start, end = A[0], A[-1]
        A = set(A)
        from functools import lru_cache
        @lru_cache(None)
        def check(pos=start, prev=0):
            if pos == end:
                return True
            for jump in (prev - 1, prev, prev + 1):
                if jump >= 1:
                    next_pos = pos + jump
                    if next_pos in A and check(next_pos, jump):
                        return True
            return False
        return check()

ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))  # Output: True

Đầu vào

[0, 1, 3, 4, 5, 6, 8, 9, 13]

Đầu ra

True