skip to content

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

/ 3 min read

Share on social media

intro-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 เยอะตาม

intro-1

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 ไปว่ายังคงตัดคำได้ไหม
  1. ตัวอย่าง 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

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

Related Post

Share on social media