Dynamic Programming 1 มิติ — พื้นฐาน & แนวคิด

Dynamic Programming (DP, การโปรแกรมแบบพลวัต) ฟังดูน่ากลัวแต่ไอเดียง่ายมาก มันคือเทคนิคแก้ปัญหาที่ปัญหาใหญ่แตกออกเป็น subproblem (ปัญหาย่อย) ที่หน้าตาเหมือนกัน และ subproblem เหล่านั้นซ้ำกันบ่อย ๆ แทนที่จะ compute (คำนวณ) คำตอบเดิมซ้ำหลายรอบ เรา compute ครั้งเดียวแล้ว cache (เก็บ) คำตอบไว้ พอต้องใช้อีกก็หยิบมาใช้ได้เลย นี่คือหัวใจทั้งหมดของ DP: จำคำตอบเก่าไว้ ไม่ทำงานซ้ำ

overlapping subproblems — สัญญาณว่าใช้ DP ได้

ลองดูตัวอย่างคลาสสิกที่สุด: เลข Fibonacci ที่ define (นิยาม) ว่า fib(n) = fib(n-1) + fib(n-2) โดย base case (กรณีฐาน) คือ fib(0) = 0 และ fib(1) = 1 ถ้าเขียนตรง ๆ ตามนิยามด้วย recursion (การเรียกตัวเอง) จะได้แบบนี้ ซึ่งช้ามาก:

def fib(n):
            if n < 2:
                return n
            return fib(n - 1) + fib(n - 2)   # ช้า! O(2^n)

ทำไมช้า? เพราะเรา compute ค่าเดิมซ้ำนับครั้งไม่ถ้วน ลองวาด recursion tree (ต้นไม้การเรียกฟังก์ชัน) ของ fib(5):

                fib(5)
              /        \
          fib(4)       fib(3)
          /    \        /    \
     fib(3)  fib(2)  fib(2) fib(1)
      ...     ...     ...
# fib(3) ถูกคำนวณ 2 ครั้ง, fib(2) ถูกคำนวณ 3 ครั้ง ...
# ยิ่ง n ใหญ่ ยิ่งซ้ำมหาศาล = overlapping subproblems

การที่ subproblem ตัวเดียวกัน (เช่น fib(3)) ถูก compute ซ้ำหลายรอบ เรียกว่า overlapping subproblems (ปัญหาย่อยที่ทับซ้อนกัน) นี่แหละคือสัญญาณว่าใช้ DP ได้ ทางแก้มีสองสไตล์ ให้ผลลัพธ์เท่ากันแต่คิดคนละทิศ

แบบที่ 1 — Memoization (top-down)

Memoization (การจดจำคำตอบ) แบบ top-down (บนลงล่าง) คือเริ่มจากปัญหาใหญ่ (fib(n)) แล้วเรียก recursion ลงไปหา subproblem ตามปกติ แต่เพิ่ม memo (สมุดโน้ต) ไว้จดคำตอบที่เคย compute แล้ว ก่อน compute อะไรก็ lookup (เปิดดู) ก่อนว่าเคยทำไว้หรือยัง ถ้าเคยก็หยิบมาใช้เลย ไม่ต้อง compute ซ้ำ

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:          # เคยคำนวณแล้ว หยิบมาใช้เลย
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)  # คำนวณแล้วจด
    return memo[n]

print(fib(10))  # 55

แบบที่ 2 — Tabulation (bottom-up)

Tabulation (การเติมตาราง) แบบ bottom-up (ล่างขึ้นบน) คือกลับด้าน เริ่มจาก subproblem ที่เล็กที่สุดก่อน (fib(0), fib(1)) แล้วค่อย ๆ ไต่ขึ้นไป build คำตอบที่ใหญ่ขึ้นทีละขั้น โดยเก็บผลลง table (ตาราง) มักเป็น array ชื่อ dp ไม่ใช้ recursion เลย

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)     # dp[i] = คำตอบของปัญหาย่อยขนาด i
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # transition: ต่อยอดจากตัวก่อนหน้า
    return dp[n]

print(fib(10))  # 55

จับ 2 อย่างนี้ให้ได้ในทุกโจทย์ DP

อีก trick (ทริค) ที่ใช้บ่อยในหมวดนี้คือ เมื่อ dp[i] depend on (พึ่งพา) แค่ค่าไม่กี่ตัวก่อนหน้า (เช่น dp[i-1], dp[i-2]) เราไม่จำเป็นต้องเก็บทั้ง array ใช้ variable (ตัวแปร) สองสามตัว rotate (หมุนค่า) แทนได้ ประหยัด Space จาก O(n) เหลือ O(1)

ในหน้านี้ทุกข้อเป็น DP แบบ 1 มิติ คือ state ใช้ index เดียว (dp[i]) พอ ในหมวดถัดไปเราจะเจอ DP ที่ state ต้องใช้สองมิติ