แนะนำหัวข้อ

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

Dynamic Programing คืออะไร ?

Dynamic Programming (DP) คือเทคนิคการเขียน algorith ที่ใช้ในการแก้ปัญหาที่ซับซ้อน โดยการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยที่เล็กลง แล้ว "แก้ปัญหาย่อยเหล่านั้นเพียงครั้งเดียว" จากนั้นจึงเก็บคำตอบของปัญหาย่อยไว้เพื่อนำมาใช้ในการแก้ปัญหาใหญ่ในภายหลัง วิธีนี้ช่วยลดการคำนวณซ้ำซ้อนและเพิ่มประสิทธิภาพในการแก้ปัญหาได้
ความแตกต่างระหว่าง Dynamic Programming เทียบกับ Divide and Conquer และ Greedy มีดังนี้

Dynamic Programming กับ Divide and Conquer:

• Divide and Conquer แบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยที่เล็กลงและแก้ปัญหาย่อยแต่ละอันแยกจากกัน ในขณะที่ Dynamic Programming แบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยที่ทับซ้อนกัน และนำผลลัพธ์ของปัญหาย่อยมาใช้ซ้ำ
• ปัญหาย่อยใน Divide and Conquer มักจะเป็นอิสระต่อกัน ไม่ทับซ้อนกัน แต่ปัญหาย่อยใน Dynamic Programming มักจะ "ทับซ้อนกัน"
• ตัวอย่างของ Divide and Conquer เช่น Merge Sort, Binary Search ส่วนตัวอย่างของ Dynamic Programming เช่น Fibonacci, Knapsack Problem

Dynamic Programming กับ Greedy:

• ทั้ง Dynamic Programming และ Greedy ต่างก็ใช้เพื่อหาคำตอบที่ดีที่สุด (optimal solution) แต่ Greedy ไม่รับประกันว่าจะได้คำตอบที่ดีที่สุดเสมอไป ในขณะที่ Dynamic Programming "รับประกันคำตอบที่ดีที่สุดเสมอ"
• Dynamic Programming เลือกทางเลือกในแต่ละขั้นตอนโดยพิจารณาจากคำตอบของปัญหาย่อย ในขณะที่ Greedy จะเลือกสิ่งที่ดูเหมือนจะเป็นทางเลือกที่ดีที่สุดในขณะนั้นโดยไม่สนใจผลในระยะยาว
• Greedy มักจะง่ายต่อการเขียนโปรแกรมมากกว่า Dynamic Programming

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

เมื่อไหร่ต้องใช้ Dynamic programming

เราควรใช้ Dynamic Programming (DP) เพื่อแก้ปัญหาเมื่อปัญหานั้นมีคุณสมบัติ 2 ประการ ได้แก่ Optimal Substructure และ Overlapping Subproblems ดังนี้

1. Optimal Substructure (โครงสร้างย่อยที่เหมาะสมที่สุด)

ปัญหาที่มี Optimal Substructure คือปัญหาที่คำตอบที่เหมาะสมที่สุด (optimal solution) ของปัญหาใหญ่ สามารถถูกสร้างขึ้นจากคำตอบที่เหมาะสมที่สุดของปัญหาย่อย กล่าวคือ เราสามารถแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยๆ แล้วหาคำตอบที่ดีที่สุดของปัญหาย่อยแต่ละอัน จากนั้นนำคำตอบเหล่านั้นมารวมกันเพื่อสร้างคำตอบที่ดีที่สุดของปัญหาใหญ่ได้
ตัวอย่างเช่น

• ปัญหาการหาเส้นทางที่สั้นที่สุด (Shortest Path Problem) - เส้นทางที่สั้นที่สุดระหว่างจุด A และ C สามารถหาได้จากเส้นทางที่สั้นที่สุดระหว่าง A กับ B และ B กับ C
• ปัญหา Longest Common Subsequence - ลำดับย่อยร่วมที่ยาวที่สุดของปัญหาใหญ่ สามารถสร้างจากลำดับย่อยร่วมที่ยาวที่สุดของปัญหาย่อยได้
• ปัญหา Longest Increasing Subsequence - ลำดับย่อยที่เพิ่มขึ้นที่ยาวที่สุดของปัญหาใหญ่ สามารถสร้างจากลำดับย่อยที่เพิ่มขึ้นที่ยาวที่สุดของปัญหาย่อยได้

2. Overlapping Subproblems (ปัญหาย่อยที่ทับซ้อนกัน)

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

• ปัญหาการหาตัวเลข Fibonacci ลำดับที่ n - ในการหา Fib(n) เราต้องเรียก Fib(n-1) และ Fib(n-2) ซ้ำหลายครั้ง ทำให้เกิดการคำนวณซ้ำซ้อน

• ปัญหา Longest Common Subsequence - ในการหาลำดับย่อยร่วมที่ยาวที่สุด เราต้องแก้ปัญหาย่อยซ้ำๆ เช่น LCS(X[1..i], Y[1..j]) จะถูกเรียกใช้หลายครั้ง

• ปัญหาการหาผลรวมของสมาชิกในอาร์เรย์ย่อย (Subset Sum Problem) - ในการหาว่ามีสมาชิกในอาร์เรย์ชุดใดบ้างที่รวมกันได้เท่ากับเป้าหมาย เราต้องแก้ปัญหาย่อยแบบเดิมซ้ำหลายรอบ

** สังเกตว่า บางปัญหาก็สามารถใช้แนวคิดทั้ง 2 อย่างแก้ปัญหาโดยมองจากไอเดีย Optimal Substructure หรือ Overlapping Subproblems โดยทั้ง 2 แนวคิดนี้ขอแค่เข้าเงื่อนไขหรือมีรูปแบบประมาณนี้อยู่ ก็สามารถใช้ Dynamic programming ในการแก้ปัญหาได้

เทียบโจทย์กับ Greedy

https://leetcode.com/problems/coin-change/description/
เราจะมาลองดูตัวอย่างผ่านโจทย์ของ Dynamic programming เบื้องต้น ผ่านโจทย์ที่เราเคยเล่าผ่านหัวข้อ Greedy กัน
ปัญหานี้ของ Leet Code คือ จะให้จำนวนเงินที่ต้องการแลกเหรียญเอาไว้ (เป็น target) และระบุเหรียญที่สามารถแลกได้ ให้ทำยังไงก็ได้ ให้แลกเหรียญโดยใช้เหรียญ "จำนวนน้อยที่สุด"

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

เช่น สมมุติ เรามีเหรียญ 1, 3, 4 บาท และเราต้องแลกเหรียญ​ 6 บาท

• หากเราใช้วิธี Greedy เราจะทำการแลกเหรียญ 4 บาทก่อนทันที (เลือกจากมากที่สุด) และจะทำการเลือกอีก 2 เหรียญคือ 1 บาท = ทั้งหมดแลกไปทั้งสิ้น 3 เหรียญ
• แต่หากเราลองดูจริงๆ วิธีการที่แลกเหรียญที่ทำให้ได้น้อยกว่า คือการแลกเหรียญ 3 บาท ทั้งหมด 2 เหรียญ นั่นเอง

นั่นเท่ากับว่า "Greedy ไม่สามารถให้คำตอบสำหรับข้อนี้ได้แล้วนั่นเอง" ดังนั้นปัญหานี้จึงจำเป็นต้อง "จดจำวิธีที่ดีที่สุด" ในการแลกแต่ละเหรียญเอาไว้ เพื่อนำมาสรุปคำตอบออกมา
ปัญหา Coin Change ใน LeetCode นั้นไม่สามารถแก้ได้ด้วยวิธี Greedy แต่สามารถแก้ได้ด้วย Dynamic Programming เพราะ

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

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

• สำหรับปัญหา Coin Change นี้ เราสามารถสร้างตารางเพื่อเก็บจำนวนเหรียญน้อยที่สุดที่ต้องใช้สำหรับแต่ละยอดเงิน โดยค่าในตารางจะขึ้นอยู่กับค่าที่คำนวณได้ก่อนหน้า ซึ่งเป็นลักษณะของ Overlapping Subproblems ใน Dynamic Programming

ปัญหานี้เราจะให้เห็นตัวอย่างปัญหาที่ไม่สามารถแก้ด้วย Greedy ได้ เราจะกลับวนมาแก้ปัญหาเมื่อเรารู้ Method ในการแก้ปัญหา Dynamic programming กันแล้วนะครับ
Step ต่อไป ทีนี้เราจะมาเรียนรู้กันบ้างว่า หากเราต้องการแก้ปัญหาด้วย Dynamic programing สามารถแก้ปัญหานี้ยังไงได้บ้างกัน