ข้อ 59 · LC1137 N-th Tribonacci Number (เลข Tribonacci ตัวที่ n) 🟢

โจทย์ (LC1137): Tribonacci sequence นิยามว่า T0 = 0, T1 = 1, T2 = 1 และ Tn+3 = Tn + Tn+1 + Tn+2 สำหรับ n >= 0 กำหนดจำนวนเต็ม n มา ให้ return ค่า Tn

แนวทาง — ต้องใช้อะไร & คิดยังไง

โจทย์นี้คือ DP 1 มิติแบบตำราเลย state คือ dp[i] = ค่า Tribonacci ตัวที่ i และ transition คือ dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ถ้าเขียนตามนิยามด้วย recursion ตรง ๆ จะช้าเป็น O(3^n) เพราะเกิด overlapping subproblems เหมือน Fibonacci เป๊ะ

เราแก้ด้วย bottom-up ได้ แต่เพราะแต่ละตัว depend on แค่สามตัวก่อนหน้าเท่านั้น จึงไม่ต้องเก็บทั้ง array ใช้ variable สามตัว (a, b, c) rotate ไปข้างหน้าก็พอ ประหยัด Space เหลือ O(1)

1. ดัก base case ให้ครบ: n = 0 return 0, n = 1 หรือ 2 return 1
2. initialize a, b, c = 0, 1, 1 แทน T0, T1, T2
3. iterate ตั้งแต่ 3 ถึง n: update ทั้งสามตัวพร้อมกันด้วย a, b, c = b, c, a + b + c
4. return c ซึ่งเป็นค่า Tn ล่าสุด

ไล่ทีละสเต็ป

ไล่ n = 4 ดูค่า a, b, c rotate ไปแต่ละรอบ:

def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:            # T1 และ T2 เท่ากับ 1
        return 1
    a, b, c = 0, 1, 1     # T0, T1, T2
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c  # เลื่อนหน้าต่างสามตัวไปข้างหน้า
    return c

print(tribonacci(4))   # 4
print(tribonacci(25))  # 1389537

4
1389537