โปรแกรมตรวจสอบว่าสามารถกระโดดถึงตำแหน่งสุดท้ายจาก Index 0 ได้หรือไม่ใน Python

สมมติว่าเรามีรายการตัวเลข nums ที่แต่ละตัวแทนจำนวนก้าวกระโดดสูงสุดจากตำแหน่งนั้น เราต้องตรวจสอบว่าสามารถไปถึง index สุดท้ายเริ่มจาก index 0 ได้หรือไม่

ตัวอย่าง: nums = [2, 5, 0, 2, 0] ผลลัพธ์ True (กระโดด 0→1 แล้ว 1→end)

ขั้นตอนการแก้ปัญหา (DP เริ่มจากท้าย - Bottom Up)

1. n = len(nums)
2. arr = [False] * n, arr[n-1] = True
3. วนลูป i จาก n-2 ถึง 0:
   • arr[i] = any(arr[i+1 : i+nums[i]+1])
4. คืนค่า arr[0]

ตัวอย่างโค้ด Python

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

อินพุต

[2, 5, 0, 2, 0]

เอาต์พุต

True