บันไดไม้สว่างบนโต๊ะมิ้นต์ มีก้าวทีละหนึ่งและสองขั้นสลับกันเป็นทางขึ้น
leetcodealgorithmsdynamic-programmingmathpythonbenchmark

LeetCode #70 Climbing Stairs: ก้าว 1 หรือ 2 แล้วจำผลย่อย

น้องกายEngineeringUpdated:

นึกถึงบันไดออฟฟิศที่ก้าวได้ทีละ 1 หรือ 2 ขั้น แล้วอยากรู้ว่ามีกี่วิธีขึ้นถึงชั้นบน โจทย์ climbing-stairs ถามจำนวนวิธีขึ้น n ขั้น โดยแต่ละก้าวเลือก 1 หรือ 2 เท่านั้น ลำดับก้าวต่างกันนับคนละวิธี

วิธีที่ 1: recursion ตรงนิยาม

จำนวนวิธีถึงขั้น n เท่ากับวิธีถึง n-1 บวกวิธีถึง n-2 เพราะก้าวสุดท้ายมาจากขั้นก่อนหน้าหนึ่งหรือสองขั้น Base case คือ n = 1 ได้ 1 ทาง และ n = 2 ได้ 2 ทาง เวลา O(2ⁿ) พื้นที่ call stack O(n) อธิบายง่าย แต่ช้ามากเมื่อ n โต

วิธีที่ 2: top-down memoization

เก็บผลของแต่ละ n ไว้ใน dict หรืออาร์เรย์ แล้ว recurse เหมือนเดิม เมื่อเจอค่าที่เคยคำนวณแล้วคืนทันที เวลา O(n) พื้นที่ O(n) ดีตอนอยากคงโครง recursion และ debug จากบนลงล่าง

วิธีที่ 3: bottom-up DP สองตัวแปร (แนะนำหลัก)

เดินจากเล็กไปใหญ่ เก็บแค่สองค่าล่าสุด a, b แทน ways(i-2) กับ ways(i-1) แล้วอัปเดต a, b = b, a + b เวลา O(n) พื้นที่ O(1) อ่านง่ายและพอสำหรับ constraints ของ LeetCode

นี่คือลำดับ Fibonacci นั่นเองครับ แค่เลื่อน index ให้ตรงกับจำนวนขั้น

วิธีที่ 4: สูตรปิด / matrix

ใช้สูตร Binet หรือยกกำลังเมทริกซ์ของ Fibonacci ได้ใกล้ O(log n) แต่ต้องระวังความแม่นยำของทศนิยมและขอบเขตจำนวนเต็ม เหมาะเมื่อ n ใหญ่มากและยอมรับความซับซ้อนเพิ่ม ไม่จำเป็นในสัมภาษณ์ข้อนี้

def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1


samples = [(1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89)]
for n, expected in samples:
    got = climb_stairs(n)
    assert got == expected, (n, got, expected)
print("ok", len(samples), "cases")

เลือกตามสถานการณ์

สถานการณ์วิธีที่เหมาะเหตุผลสั้นๆ
อธิบาย recurrence ครั้งแรกplain recursionเห็น base case ชัด
อยากคงโครง recursivememoizationO(n) โดยไม่เขียน loop
สัมภาษณ์ / โค้ดสั้นbottom-up สองตัวแปรO(n)/O(1) และพิสูจน์ง่าย
n ใหญ่มากในระบบจริงmatrix / สูตรปิดลดรอบเหลือประมาณ log n

หลุมที่ผมเคยตก: ตั้ง base case ผิด (f(0)=1 กับ f(1)=1 สลับ index), overflow ถ้าภาษาจำกัด int และลืมว่าลำดับก้าวสำคัญ ไม่ใช่แค่จำนวนก้าว 1 กับ 2

รู้จักผู้เข้าแข่งขัน

4 วิธีข้างบนยังแตกได้อีกนิดครับ bottom-up มีสองแบบ แบบแรกเก็บคำตอบทุกขั้นไว้ในตาราง dp อีกแบบเก็บแค่สองค่าล่าสุด รอบนี้ผมเลยแยกเป็น 5 วิธี ให้สัตว์ 5 ตัวมาเถียงกันว่าใครเร็วสุดที่บันได 45 ขั้น (ค่าสูงสุดที่โจทย์ยอมให้) แล้วเอา benchmark ที่วัดจริงมาตัดสิน ปิดท้ายด้วยบารอนสรุป

ตัวละครวิธีนิสัย
น้องแฮม แฮมสเตอร์สีส้มทอง คาดผ้าคาดหัวแดง เสื้อกล้ามสีฟ้า รองเท้าผ้าใบแดงrecursion ตรงนิยามไฮเปอร์ วิ่งไม่หยุด มั่นใจว่าตัวเองถูกเสมอ
ป้าช้าง ช้างใส่คาร์ดิแกนไหมพรมสีม่วงอ่อน แว่นกลม ถือสมุดจดกับดินสอmemoization (จำผลย่อย)ความจำดีแบบช้าง อะไรเคยนับแล้วจดลงสมุดหมด
พี่ผึ้ง ผึ้งตัวกลมใส่ผ้ากันเปื้อนสีมิ้นต์ ถือแผ่นรังผึ้งหกเหลี่ยมDP ตาราง (bottom-up เก็บทุกขั้น)ขยัน เป็นระเบียบ เติมรังทีละช่องจากล่างขึ้นบน
ลิงจั๊ก ลิงใส่เสื้อลายขวางส้มขาว หมวกแก๊ปกลับหลัง โยนลูกบอลสองลูกสองตัวแปรขี้เล่น ถือของแค่สองชิ้นก็พอ
จิงโจ้ จิงโจ้ใส่แจ็กเก็ตวอร์มสีเขียวอมฟ้า คาดผ้าคาดหัวขาวยกกำลังเมทริกซ์สายกระโดดไกล ชอบทางลัด
บารอน สิงโตทะเลใส่โค้ทกรมท่า เสื้อคอเต่าสีเทาอมเขียวกรรมการเข้มแต่แฟร์ ฟังตัวเลขมากกว่าเสียงดัง

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

เถียงกันทีละยก

ยกที่ 1: น้องแฮม เรียกตัวเองไปเลย

น้องแฮม: “ง่ายจะตาย! วิธีขึ้นขั้น n ก็คือวิธีขึ้นขั้นก่อนหน้า บวกวิธีขึ้นสองขั้นก่อน เรียกตัวเองไปเลย!”

ป้าช้าง: “หนูรู้ตัวไหม ที่ 45 ขั้น หนูเรียกฟังก์ชันไปกว่า 2 พันล้านครั้ง นับขั้นเดิมซ้ำไปซ้ำมา”

น้องแฮม: “ก็หนูวิ่งเร็วนี่ป้า”

ตัวเลขนี้ไม่ได้แต่งครับ ways(45) เรียก ways(44) กับ ways(43) แล้ว ways(44) ก็เรียก ways(43) ซ้ำอีกรอบ ไล่ลงไปเรื่อยๆ ways(43) ถูกคิด 2 รอบ ways(42) 3 รอบ ways(41) 5 รอบ จำนวนรอบที่ซ้ำโตเป็นลำดับ Fibonacci เหมือนคำตอบเลย รวมทั้งหมดที่ n = 45 คือ 2,269,806,339 ครั้ง (test ด้านล่างนับจากการเรียกจริงตอน n เล็ก แล้วเทียบกับสูตรที่ใช้คิดเลขนี้)

ยกที่ 2: ป้าช้าง จดลงสมุด

ป้าช้าง: “ป้าจดไว้ทุกขั้น ขั้นไหนเคยนับแล้วก็เปิดสมุดตอบเลย ไม่ต้องนับใหม่”

พี่ผึ้ง: “แต่ป้ายังเรียกตัวเองซ้อนกันลึกสี่สิบกว่าชั้นอยู่ดีนะคะ”

ป้าช้าง: “ลึกแค่นี้สบายมาก”

memoization คือจำผลของฟังก์ชันไว้ เรียกด้วยค่าเดิมอีกก็คืนค่าที่จำไว้ทันที ใน Python ใช้ functools.lru_cache แปะบนฟังก์ชันได้เลย แต่ละขั้นคิดแค่ครั้งเดียว เหลือเวลา O(n) ที่ต้องระวังคือป้าช้างยังเป็น recursion อยู่ ถ้า n เป็นหลักพันจะชนเพดานความลึกของ Python ซึ่งค่าเริ่มต้นคือ 1,000 ชั้น (ดูได้จาก sys.getrecursionlimit()) แล้วได้ RecursionError แทนคำตอบ test ด้านล่างลองที่ n = 5000 ให้เห็น

ยกที่ 3: พี่ผึ้ง เติมรังทีละช่อง

พี่ผึ้ง: “ไม่ต้องเรียกตัวเองเลยค่ะ เติมรังจากช่อง 1 ขึ้นไปทีละช่อง ช่องใหม่ก็เอาสองช่องข้างล่างมาบวกกัน”

ลิงจั๊ก: “แล้วพี่จะเก็บทั้งรังไว้ทำไม ช่องใหม่ใช้แค่สองช่องล่าสุดเอง”

พี่ผึ้ง: “เผื่อมีคนถามคำตอบขั้นอื่นไง”

dp เป็น list ยาว n + 1 ช่อง ช่อง dp[i] คือจำนวนวิธีขึ้นขั้น i เวลา O(n) ที่เพิ่ม O(n) ไม่มี recursion เลยไม่ชนเพดานแบบป้าช้าง และได้คำตอบของทุกขั้นติดมือมาด้วย ถ้าโจทย์ถามต่อว่า “ขอจำนวนวิธีของทุกขั้นตั้งแต่ 1 ถึง n” พี่ผึ้งตอบได้ทันที

ยกที่ 4: ลิงจั๊ก โยนแค่สองลูก

ลิงจั๊ก: “เห็นไหม ผมโยนลูกบอลแค่สองลูก ลูกเก่าส่งต่อ ลูกใหม่คือผลบวกของสองลูก a, b = b, a + b จบ”

จิงโจ้: “ยังต้องเดินทีละขั้นอยู่ดี ช้าไป!”

นี่คือวิธีที่ 3 ข้างบนครับ เก็บแค่สองค่าล่าสุด เวลา O(n) ที่เพิ่ม O(1) โค้ดสั้น พิสูจน์ง่าย

ยกที่ 5: จิงโจ้ กระโดดทีละเท่าตัว

จิงโจ้: “ผมไม่เดินทีละขั้นหรอก ยกกำลังเมทริกซ์ กระโดดทีละเท่าตัว 45 ขั้นวนแค่ 6 รอบ!”

ลิงจั๊ก: “รอบน้อยก็จริง แต่แต่ละรอบพี่แบกของหนักนะ”

เมทริกซ์ [[1, 1], [1, 0]] ยกกำลัง k จะได้เลข Fibonacci ตัวที่ k อยู่ในช่องขวาบน ยกกำลังแบบยกกำลังสองซ้ำ (เลขชี้กำลังลดครึ่งทุกรอบ) จึงใช้แค่ประมาณ log n รอบ ที่ n = 45 โค้ดนี้หา F(46) วน 6 รอบ แต่คูณเมทริกซ์ 2×2 รวม 10 ครั้ง ครั้งละคูณเลข 8 ตัว และสร้าง tuple ใหม่ทุกครั้ง ส่วนลิงจั๊กแค่บวกเลข 43 ครั้ง จำตรงนี้ไว้ เดี๋ยวได้ใช้ตอนดูผล

โค้ดทั้ง 5 วิธีพร้อม test

บล็อกนี้รันจริงตอนตรวจบทความ ทดสอบทุกวิธีกับตัวอย่าง เช็กว่าทุกวิธีตอบตรงกันตั้งแต่ 1 ถึง 25 ขั้น เช็กคำตอบที่ 45 ขั้น นับจำนวนครั้งที่น้องแฮมเรียกตัวเอง และลองให้ป้าช้างชนเพดาน recursion

import unittest
from functools import lru_cache


def climb_recursive(n):
    if n <= 2:
        return n
    return climb_recursive(n - 1) + climb_recursive(n - 2)


def climb_memo(n):
    @lru_cache(maxsize=None)
    def ways(k):
        if k <= 2:
            return k
        return ways(k - 1) + ways(k - 2)
    return ways(n)


def climb_table(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


def climb_two_vars(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1


def climb_matrix(n):
    def mul(a, b):
        return ((a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]),
                (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]))
    result, base, k = ((1, 0), (0, 1)), ((1, 1), (1, 0)), n + 1
    while k:
        if k & 1:
            result = mul(result, base)
        base = mul(base, base)
        k >>= 1
    return result[0][1]  # F(n + 1) = ways(n)


ALL = [climb_recursive, climb_memo, climb_table, climb_two_vars, climb_matrix]


def calls_recursive(n):
    """Count how many calls plain recursion makes for n."""
    if n <= 2:
        return 1
    return 1 + calls_recursive(n - 1) + calls_recursive(n - 2)


def calls_loop(n):
    """Same count without recursion: calls(n) = 1 + calls(n - 1) + calls(n - 2)."""
    a, b = 1, 1
    for _ in range(3, n + 1):
        a, b = b, 1 + a + b
    return b


class TestClimbStairs(unittest.TestCase):
    def test_examples(self):
        samples = [(1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89)]
        for fn in ALL:
            for n, expected in samples:
                with self.subTest(fn=fn.__name__, n=n):
                    self.assertEqual(fn(n), expected)

    def test_all_agree(self):
        for n in range(1, 26):
            self.assertEqual(len({fn(n) for fn in ALL}), 1, n)

    def test_max_n(self):
        # plain recursion at n = 45 takes tens of seconds, so it is skipped here
        for fn in ALL[1:]:
            self.assertEqual(fn(45), 1_836_311_903)

    def test_recursive_call_count(self):
        for n in range(1, 25):
            self.assertEqual(calls_recursive(n), calls_loop(n))
        self.assertEqual(calls_loop(45), 2_269_806_339)

    def test_answer_fits_int32_up_to_45(self):
        self.assertLess(climb_two_vars(45), 2**31 - 1)
        self.assertGreater(climb_two_vars(46), 2**31 - 1)

    def test_memo_hits_recursion_limit(self):
        with self.assertRaises(RecursionError):
            climb_memo(5000)
        self.assertEqual(climb_table(5000), climb_two_vars(5000))
        self.assertEqual(climb_matrix(5000), climb_two_vars(5000))


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

test_answer_fits_int32_up_to_45 มีไว้ตอบหลุม overflow ที่เล่าไว้ข้างบนครับ คำตอบที่ 45 ขั้นคือ 1,836,311,903 ยังไม่เกิน int 32 บิต (สูงสุด 2,147,483,647) แต่ขั้นที่ 46 ได้ 2,971,215,073 เกินแล้ว ภาษาอย่าง Java หรือ C++ ที่ใช้ int จึงพอดีกับโจทย์นี้แบบเฉียดๆ ส่วน Python ไม่มีปัญหาเพราะ int ใหญ่ได้ไม่จำกัด

benchmark ตัดสิน

บารอน: “พอได้แล้ว เถียงกันไปก็ไม่จบ ใครเร็วจริงไปวัดมาให้ดู”

วัดบน Mac ชิป Apple M5 Pro ด้วย Python 3.15.0 (CPython) ใช้ timeit เรียกแต่ละวิธีที่ n = 45 ซ้ำ 20,000 ครั้งต่อรอบ ทำ 5 รอบ แล้วเอารอบที่เร็วที่สุดหารด้วย 20,000 เป็นเวลาต่อการเรียกหนึ่งครั้ง (เอกสาร timeit แนะนำให้ดูค่าต่ำสุด เพราะค่าที่สูงกว่านั้นมักโดนงานอื่นในเครื่องรบกวน ไม่ได้มาจากโค้ดเอง) ส่วนน้องแฮมวัดแค่ครั้งเดียว เพราะครั้งเดียวก็เกือบ 40 วินาทีแล้ว ก่อนจับเวลาทุกวิธีต้องตอบ 1,836,311,903 ให้ถูกก่อน และป้าช้างสร้างสมุดใหม่ทุกครั้งที่ถูกเรียก ไม่ได้แอบใช้คำตอบที่จำไว้จากรอบก่อน

โค้ดด้านล่างเป็นโค้ดบางส่วน ไม่ได้รันตอนตรวจบทความ ใช้ฟังก์ชันจากบล็อกด้านบนที่เซฟเป็นไฟล์ solutions.py

import timeit
from solutions import ALL, climb_recursive

n = 45
for fn in ALL:
    number, repeat = (1, 1) if fn is climb_recursive else (20_000, 5)
    assert fn(n) == 1_836_311_903
    best = min(timeit.repeat(lambda: fn(n), number=number, repeat=repeat)) / number
    print(f"{fn.__name__:16s} {best * 1e6:,.2f} µs")

µs คือไมโครวินาที หรือหนึ่งในล้านวินาทีครับ

ตัวละคร (วิธี)เวลาต่อการเรียก 1 ครั้งช้ากว่าลิงจั๊ก
น้องแฮม (recursion)38.99 วินาทีราว 90 ล้านเท่า
ป้าช้าง (memo)4.94 µs11.5 เท่า
พี่ผึ้ง (DP ตาราง)0.84 µs2.0 เท่า
ลิงจั๊ก (สองตัวแปร)0.43 µs—
จิงโจ้ (matrix)1.79 µs4.2 เท่า

ผมรันชุดเดียวกันซ้ำอีกรอบ ตัวเลขขยับไปไม่กี่เปอร์เซ็นต์ แต่อันดับเหมือนเดิมทุกตัว ตัวเลขทั้งหมดมาจากเครื่องเดียว เครื่องอื่นหรือ Python เวอร์ชันอื่นจะได้ค่าไม่เท่านี้ สิ่งที่เห็นจากการวัดคือ

  • น้องแฮมช้ากว่าลิงจั๊กราว 90 ล้านเท่า (38.99 วินาที ÷ 0.43 µs) นี่คือราคาของการเรียกฟังก์ชัน 2,269,806,339 ครั้ง เทียบกับการบวกเลข 43 ครั้ง
  • ป้าช้างกับพี่ผึ้ง Big-O เท่ากันคือ O(n) แต่ป้าช้างช้ากว่าราว 6 เท่า (4.94 กับ 0.84 µs) ผมเดาว่าเป็นค่าเรียกฟังก์ชันซ้อน 44 ชั้นกับการสร้าง cache ใหม่ทุกครั้ง แต่ข้อนี้ไม่ได้วัดแยกให้เห็น
  • พี่ผึ้งช้ากว่าลิงจั๊กราว 2 เท่า เพราะต้องสร้าง list 46 ช่องแล้วอ่านเขียนผ่าน index ส่วนลิงจั๊กแค่สลับสองตัวแปร
  • จิงโจ้ที่ Big-O ดีที่สุด (O(log n)) กลับช้ากว่าลิงจั๊กราว 4 เท่า เพราะบันไดแค่ 45 ขั้น จำนวนรอบที่ประหยัดได้ยังไม่คุ้มกับงานต่อรอบที่หนักกว่ามาก (คูณเมทริกซ์ 10 ครั้งกับบวกเลข 43 ครั้ง)
  • ถ้า n ใหญ่ระดับแสนหรือล้าน ตามทฤษฎีจิงโจ้จะเริ่มได้เปรียบ เพราะเลขจะยาวมากและจำนวนรอบต่างกันเยอะ แต่รอบนี้ไม่ได้วัด ผมเลยไม่ใส่ตัวเลข

จิงโจ้: “เอ๊ะ! ผมกระโดดไกลกว่า ทำไมแพ้ลิง?”

บารอน: “บันไดแค่ 45 ขั้น คูณเมทริกซ์งานเยอะกว่าบวกเลข”

น้องแฮม: “หนูขอไปนั่งพักก่อนนะ วิ่งมาสองพันล้านรอบแล้ว”

บารอนสรุป

บารอน: “ฟังนะ ทุกคนตอบ 1,836,311,903 วิธีถูกหมด แต่เร็วไม่เท่ากัน

น้องแฮมเอาไว้อธิบาย recurrence ตอนเริ่ม แล้วต้องบอกเองว่ามันเป็น O(2ⁿ) ใช้จริงไม่ได้ ป้าช้างดีตอนอยากคงโครง recursion ไว้ แต่ถ้า n เป็นหลักพันจะชนเพดานของ Python พี่ผึ้งเหมาะตอนโจทย์อยากได้คำตอบของทุกขั้น ส่วนจิงโจ้เก็บไว้คุยตอนเขาถามต่อว่าถ้า n เป็นล้านจะทำยังไง

คำตอบหลักตอนสัมภาษณ์คือลิงจั๊ก เวลา O(n) หน่วยความจำ O(1) วัดจริงก็เร็วสุด ลิงชนะ!”

วิธีเวลาที่เพิ่มวัดจริงที่ n = 45ใช้เมื่อ
น้องแฮม (recursion)O(2ⁿ)O(n) call stack38.99 วินาทีอธิบาย recurrence ครั้งแรก
ป้าช้าง (memo)O(n)O(n)4.94 µsอยากคงโครง recursive และ n ไม่ใหญ่
พี่ผึ้ง (DP ตาราง)O(n)O(n)0.84 µsต้องการคำตอบของทุกขั้น
ลิงจั๊ก (สองตัวแปร)O(n)O(1)0.43 µsคำตอบหลักตอนสัมภาษณ์
จิงโจ้ (matrix)O(log n) รอบการคูณO(1)1.79 µsn ใหญ่มาก (ยังไม่ได้วัดในบทความนี้)

Recap

  • เขียน recurrence: ways(n) = ways(n-1) + ways(n-2)
  • ตั้ง base 1 → 1, 2 → 2 ให้ถูก
  • ใช้สองตัวแปรอัปเดตจากเล็กไปใหญ่
  • เทียบกับค่า Fibonacci ที่รู้จักก่อนเชื่อโค้ด
  • วัดจริงที่ 45 ขั้น: สองตัวแปร 0.43 µs ส่วน recursion เปล่า 38.99 วินาที
  • O(log n) ไม่ได้ชนะเสมอ ตอน n เล็ก งานต่อรอบสำคัญกว่าจำนวนรอบ
  • default เลือก bottom-up O(n)/O(1) ครับ