แนะนำ Dynamic programming แบบนิ่มนวลที่สุด

สามารถดู video ของหัวข้อนี้ก่อนได้ ดู video

Dynamic programming คืออะไร ?

Dynamic programming คือ เทคนิคหนึ่งที่ใช้สำหรับแก้ปัญหาที่ ปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) โดยการพยายามแก้ปัญหาย่อยก่อน แล้วค่อยมาสู่การแก้ปัญหาที่ใหญ่ขึ้น

ใน ครั้งนี้ผมจะหยิบ 2 เทคนิคนี้มาอธิบายคือ

1. Memorization (Top-down approach) คือ ทำอะไรไว้ก็จำด้วย จะได้ไม่ต้องทำปัญหาย่อยซ้ำ เพื่อให้คิดวิธีแก้ปัญหาใหญ่ได้ไวขึ้น
2. Tabulation (Bottom-up approach) คือ ทำจากอะไรเล็กๆก่อน (ที่เป็นคำตอบที่ดีที่สุดของปัญหานั้น) แล้วค่อยมารวมกันตอบปัญหาใหญ่อีกที

เริ่มต้นกับตัวอย่าง fibonacci

Recursive แบบปกติ

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

ปัญหาอยู่ที่

• ต้องพิจารณาทุกเคส
• เกิดเคสทำซ้ำเกิดขึ้น

ปัญหาของเรื่องนี้เราต้องวัดกันที่ Big O

Big O คือ complexity ของ algorithm ยิ่งเยอะ = ยิ่ง operation เยอะตาม

Ref: https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/

ถ้า list มาเฉพาะ Big O ที่เราจะได้วิเคราะห์จะเหลือเพียง

• O(1) = Constant (ไม่ว่าจะใส่อะไรเข้าไปก็ทำเพียงคำสั่งเดียว เช่น +, - เลข)
• O(log n) = เวลาลดลงครึ่งหนึ่งในทุกรอบที่ทำ
• O(n) = linear time = loop เดียว
• O(n^2) = 2 loop
• O(2^n) = เช็คใช่ไม่ใช่ทุกเคส

Fibo แบบ recursive = O(2^n)

DP Memorization - Top-down Dynamic Programming

• ทำอะไรไปแล้วก็จำ
• เช่น ถ้าเกิดว่า fibo(3) ถูกคิดไปแล้วจากตอน recursive ครั้งไหน = ให้เก็บไว้ใน memo[3]
• เพื่อที่ตอนที่วน recursive กลับมาจาก fibo(3) จากตัวอื่น จะได้สามารถเรียกใช้จาก memo[3] แทนที่จะต้องไปคำนวนใหม่

code ตัวอย่าง

def fibonacci_memoization(n, memo={}):
  if n in memo:
    return memo[n]
  if n <= 1:
    return n
  memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
  return memo[n]

DP Tabulation - Bottom-Up Dynamic Programming

• ทำจากเล็กๆแล้วไล่ไปจนถึงเป้าหมาย
• เช่นจากเคสนี้คือ เราจะเริ่มทำจาก fibo(1) -> fibo(2) … -> fibo(n) และนำ fibo(n) ที่เก็บใน array มาตอบแทน

code ตัวอย่าง

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

ตัวอย่างจากโจทย์ใน leet code

ที่ผมเลือกหยิบเป็น 2 ข้อนี้มา เพราะมี solution แปะไว้อยู่แล้วใน leetcode เช่นกัน อาจจะไม่ได้ใช้วิธีที่ผมใช้ซะทีเดียว แต่สามารถนำไปเรียนรู้ประกอบได้

1. โจทย์ Memorization Word Break https://leetcode.com/problems/word-break

Note

• ถ้าทำแบบปกติทั่วไป จะต้องเช็ค เอา / ไม่เอา = ใช้ O(2^n)
• ถ้าทำแบบ DP คือ
  • เราจะจำตำแหน่งก่อนหน้าว่าตัดสำเร็จหรือไม่ = ถ้าสำเร็จให้บอกตำแหน่งถัดไปเพื่อบอกว่า ก่อนหน้านี้เราตัดสำเร็จแล้ว
  • เพื่อที่จะได้ไม่ต้องวนเช็คทุก combination ได้
  • Big O จะเหลือเพียง O(n^2) โดย n คือขนาดของ string s แทน

code solution ของ ข้อนี้

class Solution:
  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    memo = [False] * (n+1) # ใช้ n+1 เพราะตอนขนาด string index n เราจะบันทึกที่ช่อง n ของ memo
    memo[0] = True

    for end in range(1, n+1):
      for start in range(end):
        if memo[start] and s[start:end] in word_set:
          memo[end] = True
          break

    return memo[n]

Solution

• เก็บ memo เอาไว้ว่าแต่ละ index เคยเจอไหม
• ถ้าปลายเจอ = จำไว้ว่าสามารถเจอคำนี้ได้
• ส่งคำตอบเป็นตำแหน่งสุดท้ายของ array ไปว่ายังคงตัดคำได้ไหม

2. ตัวอย่าง Tabulation Generate Parentheses https://leetcode.com/problems/generate-parentheses/

Note

• ถ้าทำแบบปกติทั่วไป ต้องเช็คทุกเคสว่า วางวงเล็บ / ไม่วางวงเล็บ = เช็คว่าเอา / ไม่เอา = O(2^n)
• ถ้าทำแบบ DP
  • เราจะเริ่มทำจาก () ที่สำเร็จก่อนที่ n = 1
  • หลังจากนั้นเราจะค่อยๆประกอบ () มาจาก assamption ที่ว่า วงเล็บจะยังคงเป็นวงเล็บที่ถูกต้องเสมอ ถ้าเราเอา () อะไรก็ตามมาวางไว้ตรงกลาง หรือ ด้านข้าง แบบนี้ (_)_
  • เช่น n = 2 จะต้องมี () ทั้งหมด 2 อัน เราก็จะทำ () ไปแทนที่ตำแหน่ง _ ในแต่ละเคสโดย ()() เมื่อ _ แรก = ” และ _ ที่สอง = (), (()) เมื่อ _ แรก = () และ _ ที่สอง = ()
  • Big O จะเหลือเพียงราวๆ O(n^2) ได้โดย n คือจำนวนวงเล็บที่ต้องการ

code solution ของข้อนี้

class Solution:
  def generateParenthesis(self, n: int) => List[str]:
    if n == 0:
      return [""]
    dp = [[] for _ in range(n+1)]
    dp[0] = [""]
    for i in range(1, n+1):
      for j in range(i):
        for left in dp[j]:
          for right in dp[i - j - 1]:
            print(i, "(" + left + ")" + right)
            dp[i].append("(" + left + ")" + right)
    return dp[n]

Solution

• เริ่มทำจาก 1 วงเล็บ, 2 วงเล็บ จนถึง n วงเล็บ
• ทุกๆการประกอบวงเล็บเราจะวนกลับไปใช้วงเล็บเดิมมาประกอบ เช่น 3 วงเล็บเกิดจาก 0 วงเล็บ + 2 วงเล็บ, 1 วงเล็บ + 1 วงเล็บ (ที่มาของ loop i, j)
• คำตอบจะอยู่กับตำแหน่ง array สุดท้าย (ตำแหน่งที่ n)

Note ส่งท้าย

นี่ยังเป็นเพียงเรื่องเล็กๆของ Dynamic Programming จริงๆ มันยังมีเนื้อหาและโจทย์น่าสนใจให้ลองทำดู

• ยังมีปัญหาท้าทายใน Dynamic Programming อีกมากเช่น
  • Knapsacks
  • Longest common subsequence (LCS)
  • Longest Increasing Subsequence
  • Maximum Subarray Sum

หาอ่านเพิ่มเติมกันได้ที่

• https://www.geeksforgeeks.org/dynamic-programming/
• https://medium.com/@aquablitz11/an-introduction-to-dynamic-programming-76574fda6501