LeetCode 55 Jump Game: ไปถึงปลายทางด้วย greedy แบบไม่แบกตาราง

โจทย์ Jump Game ให้ array จำนวนก้าวสูงสุดจากแต่ละตำแหน่ง แล้วถามว่าเริ่มช่องแรกจะไปถึงช่องสุดท้ายได้หรือไม่ครับ เราเลือกกระโดดสั้นกว่าค่าสูงสุดได้ จึงไม่ต้องจำทุกเส้นทาง

สรุปโจทย์ด้วยคำของเรา

แต่ละช่องเป็นปั๊มน้ำมันที่บอกระยะทางสูงสุด ไม่ได้บังคับให้ขับจนสุด เป้าหมายคือรู้ว่าแนวหน้าที่ไปถึงได้ขยายครอบปลายทางหรือเจอช่องที่อยู่เลยแนวหน้า

วิธีที่ 1: forward maximum reach

เดินซ้ายไปขวาและเก็บ index ไกลสุด farthest หาก index ปัจจุบันมากกว่า farthest แปลว่าเราเดินมาถึงช่องที่เข้าถึงไม่ได้

• เวลา O(n) หน่วยความจำ O(1)
• อ่านง่ายและหยุดเร็วเมื่อเจอ gap
• ไม่แก้ input และเหมาะเป็น default

วิธีที่ 2: backward goal

เริ่ม goal ที่ช่องสุดท้าย เดินย้อนกลับ หากตำแหน่งใดกระโดดถึง goal ได้ ให้ย้าย goal มาที่ตำแหน่งนั้น สุดท้าย goal ต้องกลับมาศูนย์

• เวลา O(n) หน่วยความจำ O(1)
• proof สั้นและไม่มี arithmetic ของ frontier หลายค่า
• ต้องมี random access จึงไม่เหมาะกับ streaming input

วิธีที่ 3: dynamic programming

เก็บ boolean ว่าแต่ละช่องเข้าถึงได้ แล้วกระจายไปข้างหน้า วิธีนี้ตรงกับนิยามแต่ทำงานสูงสุด O(n²) และใช้ O(n) memory เหมาะเป็น oracle สำหรับ test หรือเมื่อโจทย์ต่อยอดให้ต้องนับ/คืนเส้นทาง

import unittest


def can_jump_forward(nums):
    farthest = 0
    for index, jump in enumerate(nums):
        if index > farthest:
            return False
        farthest = max(farthest, index + jump)
        if farthest >= len(nums) - 1:
            return True
    return bool(nums)


def can_jump_backward(nums):
    if not nums:
        return False
    goal = len(nums) - 1
    for index in range(goal - 1, -1, -1):
        if index + nums[index] >= goal:
            goal = index
    return goal == 0


def can_jump_dp(nums):
    if not nums:
        return False
    reachable = [False] * len(nums)
    reachable[0] = True
    for index, ok in enumerate(reachable):
        if not ok:
            continue
        for nxt in range(index + 1, min(len(nums), index + nums[index] + 1)):
            reachable[nxt] = True
    return reachable[-1]


class JumpGameTests(unittest.TestCase):
    def check(self, nums, expected):
        self.assertEqual(can_jump_forward(nums), expected)
        self.assertEqual(can_jump_backward(nums), expected)
        self.assertEqual(can_jump_dp(nums), expected)

    def test_reachable_and_blocked(self):
        self.check([2, 3, 1, 1, 4], True)
        self.check([3, 2, 1, 0, 4], False)

    def test_boundaries(self):
        self.check([0], True)
        self.check([], False)
        self.check([2, 0, 0], True)


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	Forward reach	Backward goal	DP
input ใหญ่	ดีที่สุด	ดีที่สุด	หลีกเลี่ยง
memory จำกัด	O(1)	O(1)	O(n)
streaming ซ้ายไปขวา	เหมาะที่สุด	ไม่เหมาะ	ไม่เหมาะ
readability	เห็น frontier ชัด	proof สั้น	ตรงนิยาม
ต้องคืนเส้นทางภายหลัง	ต้องเพิ่ม parent	ต้องเพิ่มข้อมูล	ต่อได้ง่ายกว่า
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่าน

Best default: forward maximum reach เพราะ O(n), O(1), หยุดเร็ว และรองรับข้อมูลที่ไหลจากซ้ายไปขวา

Edge cases

• array ช่องเดียวถึงเป้าหมายแล้วแม้ค่าเป็นศูนย์
• array ว่างไม่ได้อยู่ใน constraints ปกติ แต่ helper ควรกำหนด contract
• ศูนย์กลางทางไม่ใช่ปัญหาหาก frontier กระโดดข้ามได้
• ภาษา integer คงที่ต้องระวัง index + jump overflow หาก constraints ใหญ่กว่าปกติ

Recap

• เก็บ “ไกลสุดที่ถึงได้” ไม่ต้องลองทุกเส้นทาง
• ถ้า index เกิน frontier ให้ตอบ false ทันที
• backward goal เป็นทางเลือกที่ proof กระชับ
• DP ใช้เป็น oracle/โจทย์ต่อยอด ไม่ใช่ default