Chương trình kiểm tra có thể đến vị trí cuối từ chỉ số 0 trong Python

Cho danh sách với là số bước nhảy tối đa từ vị trí i. Kiểm tra có thể nhảy từ index 0 đến index cuối cùng hay không.

Ví dụ: → True (nhảy 0→1→cuối).

Giải thuật (DP ngược - O(n²) worst case)

1. , mảng boolean kích thước , .
2. Duyệt từ xuống 0:
   • (có vị trí nào trong phạm vi nhảy dẫn đến đích không).
3. Trả về .

Có thể tối ưu O(n) bằng biến theo dõi vị trí cuối cùng có thể đến đích.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        n = len(nums)
        arr = [False] * n
        arr[n - 1] = True
        for i in range(n - 2, -1, -1):
            arr[i] = any(arr[i + 1 : i + nums[i] + 1])
        return arr[0]

ob = Solution()
nums = [2, 5, 0, 2, 0]
print(ob.solve(nums))  # Output: True

Đầu vào

[2,5,0,2,0]

Đầu ra

True