Dynamic Programming คืออะไร — อธิบาย Memoization และ Tabulation

Dynamic programming คือวิธีแก้ปัญหาโดยเก็บคำตอบของปัญหาย่อยที่เล็กกว่าไว้ แล้วนำกลับมาใช้ซ้ำในภายหลัง วิธีนี้มีประโยชน์เมื่อปัญหาย่อยเดิมเกิดขึ้นซ้ำ และคำตอบสุดท้ายสามารถประกอบขึ้นจากคำตอบย่อยเหล่านั้นได้

แนวทางหลักมีอยู่ 2 แบบคือ memoization และ tabulation โดย memoization จะเก็บคำตอบระหว่างการแก้แบบ recursive ส่วน tabulation จะเติมคำตอบจากล่างขึ้นบน โดยมักใช้ array หรือตาราง

Dynamic programming ใช้ได้เมื่อไร

Dynamic programming มีประโยชน์เมื่อมีเงื่อนไข 2 ข้อ

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

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

Memoization กับ tabulation ต่างกันอย่างไร

Memoization: เก็บค่าแบบบนลงล่าง

Memoization เริ่มจากแนวคิดแบบ recursive เมื่ออัลกอริทึมแก้ปัญหาย่อยครั้งแรก ก็จะเก็บผลลัพธ์นั้นไว้ การเรียกครั้งถัดไปจะนำค่าที่เก็บไว้มาใช้แทนการคำนวณใหม่

แนวทางนี้มักเข้าใจง่ายกว่าเมื่อความสัมพันธ์เวียนเกิดชัดเจน แต่ลำดับของสถานะทั้งหมดที่ต้องใช้ยังไม่ชัด

Tabulation: สร้างคำตอบแบบล่างขึ้นบน

Tabulation เริ่มจากกรณีฐาน แล้วเติมสถานะต่าง ๆ ตามลำดับที่ทำให้ค่าที่ต้องพึ่งพามีพร้อมใช้เมื่อจำเป็น

แนวทางนี้มักง่ายกว่าเมื่อคุณรู้ลำดับการวนซ้ำที่ชัดเจนอยู่แล้ว และต้องการควบคุมตารางอย่างตรงไปตรงมา

ตัวอย่าง Dynamic programming: Fibonacci

ลำดับฟีโบนัชชีนิยามโดย

$$F(0) = 0, \quad F(1) = 1$$

และสำหรับ $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

วิธี recursive แบบตรงไปตรงมาจะคำนวณซ้ำ ตัวอย่างเช่น การหา $F(5)$ ต้องใช้ $F(4)$ และ $F(3)$ แล้วการหา $F(4)$ ก็ต้องใช้ $F(3)$ อีกครั้ง การเรียก $F(3)$ ซ้ำนี้คือความสูญเปล่าที่ dynamic programming ช่วยตัดออก

ใช้ memoization กับ Fibonacci

เมื่อใช้ memoization ความสัมพันธ์เวียนเกิดยังเหมือนเดิม แต่แต่ละค่าจะถูกเก็บไว้หลังจากคำนวณครั้งแรก

สำหรับ $F(5)$ ลำดับที่เป็นประโยชน์คือ:

• คำนวณและเก็บ $F(0)=0$
• คำนวณและเก็บ $F(1)=1$
• คำนวณและเก็บ $F(2)=1$
• คำนวณและเก็บ $F(3)=2$
• คำนวณและเก็บ $F(4)=3$
• คำนวณและเก็บ $F(5)=5$

ประเด็นสำคัญคือแต่ละสถานะถูกคำนวณเพียงครั้งเดียว หลังจากนั้นการเรียกใช้จะอ่านค่าที่เก็บไว้

ใช้ tabulation กับ Fibonacci

เมื่อใช้ tabulation คุณจะสร้างคำตอบจากกรณีฐานขึ้นไป:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

เวอร์ชันนี้ทำให้ลำดับการพึ่งพาชัดเจนมาก เพราะค่าใหม่แต่ละค่าจะใช้รายการที่รู้ค่าอยู่แล้ว

ทำไม dynamic programming จึงเร็วขึ้นได้

ถ้าปัญหาหนึ่งมีเพียง $k$ สถานะที่แตกต่างกันและมีความสำคัญ Dynamic programming จะพยายามแก้ทั้ง $k$ สถานะนั้นอย่างละหนึ่งครั้ง วิธีนี้สามารถเปลี่ยนต้นไม้การเรียก recursive ขนาดใหญ่ให้กลายเป็นการคำนวณที่เล็กลงมาก

ความเร็วที่เพิ่มขึ้นจริงขึ้นอยู่กับลักษณะของปัญหา Dynamic programming ไม่ได้เร็วเสมอไปโดยอัตโนมัติ มันช่วยได้เมื่อการคำนวณซ้ำเป็นส่วนสำคัญของวิธีแก้เดิมจริง ๆ

ข้อผิดพลาดที่พบบ่อยใน Dynamic programming

ใช้ทั้งที่ปัญหาย่อยไม่ได้ซ้ำกัน

ไม่ใช่ทุกปัญหาแบบ recursive จะเป็นปัญหา dynamic programming ถ้าปัญหาย่อยแทบทุกอันแตกต่างกัน การ cache ผลลัพธ์อาจช่วยลดงานได้ไม่มากพอจะเห็นผล

กำหนดสถานะผิด

สถานะต้องมีข้อมูลครบทุกอย่างที่จำเป็นสำหรับขั้นถัดไป ถ้าข้อมูลสำคัญหายไป ความสัมพันธ์เวียนเกิดอาจดูเหมือนถูกต้อง แต่ให้คำตอบผิดได้

กำหนดกรณีฐานผิด

กรณีฐานเป็นจุดยึดของวิธีทั้งหมด ถ้าค่าเริ่มต้นผิด ทุกสถานะถัดไปที่สร้างจากมันก็จะผิดตามไปด้วย

เติมตารางผิดลำดับ

Tabulation จะทำงานได้ก็ต่อเมื่อแต่ละสถานะถูกเติมหลังจากสถานะที่มันต้องพึ่งพาแล้วเท่านั้น ต่อให้ความสัมพันธ์เวียนเกิดถูกต้อง ก็ยังล้มเหลวได้ถ้าลำดับการเติมผิด

คิดว่า dynamic programming ต้องเป็นโจทย์ optimization เสมอ

ตัวอย่างที่มีชื่อเสียงหลายข้อเป็นการหาค่าสูงสุดหรือค่าต่ำสุด แต่ dynamic programming ยังใช้กับปัญหาการนับและปัญหาการตัดสินใจได้ด้วย สัญญาณที่แท้จริงคือมีปัญหาย่อยที่นำกลับมาใช้ซ้ำได้ ไม่ใช่คำว่า "ดีที่สุด"

Dynamic programming ใช้ที่ไหนบ้าง

Dynamic programming ปรากฏในโจทย์อย่างเช่น edit distance, longest common subsequence, การนับจำนวนเส้นทาง, การหาค่าเหมาะที่สุดแบบ knapsack และปัญหา shortest path บางกรณี

เมื่อคุณกำลังตัดสินใจว่าจะลองใช้วิธีนี้หรือไม่ ให้ถาม 2 คำถาม:

• ปัญหาย่อยที่เล็กกว่ามีการเกิดซ้ำหรือไม่?
• คำตอบที่ใหญ่กว่าสามารถสร้างจากคำตอบย่อยเหล่านั้นได้หรือไม่?

ถ้าคำตอบของทั้งสองข้อคือใช่ Dynamic programming ก็เป็นตัวเลือกที่น่าสนใจมาก

ลองทำโจทย์ที่คล้ายกัน

ลองทำเวอร์ชันของคุณเองกับโจทย์หาจำนวนวิธีเดินขึ้นบันได $n$ ขั้น เมื่อแต่ละครั้งเดินได้ $1$ ขั้นหรือ $2$ ขั้น ความสัมพันธ์เวียนเกิดของโจทย์นี้เรียบง่าย มองเห็นปัญหาย่อยที่ซ้ำกันได้ง่าย และเป็นตัวอย่างถัดไปที่ดีหลังจาก Fibonacci