อ่านบทความนี้ใน Facebook
“คุณเป็นเจ้าของร้านรับแลกเหรียญแห่งหนึ่ง เพื่อรับแลกเงิน \(n\) บาทจากลูกค้าให้เปลี่ยนเป็นเหรียญ 1, 3, 4 บาท”
เพื่อประสบการณ์ที่ดีที่สุดของลูกค้า คุณเลยตั้งกฏว่าจะต้องแลกเหรียญให้ได้จำนวนเหรียญที่น้อยที่สุดเสมอ (เช่นคนมาแลก 100 บาท เราคงจะไม่ให้เหรียญ 1 บาท 100 เหรียญ 😆)
ลูกค้าคนแรกบอกว่าขอแลกเงิน 7 บาท: แน่นอนว่าเราไม่รู้ว่าเราจะแลกเหรียญให้ได้จำนวนน้อยที่สุดอย่างไร ดังนั้นวิธีการนึงก็คือการลองครับ
ถ้าใช้แต่เหรียญ 1 บาทจะต้องใช้ 7 เหรียญ; ถ้าใช้เหรียญ 3 กับ 1 จะต้องใช้ 3 เหรียญ; …ถ้าเราใช้เหรียญ 4 กับ 3 เราจะใช้แค่ 2 เหรียญเท่านั้น ซึ่งน้อยที่สุด
ลูกค้าคนที่สองบอกว่าขอแลกเงิน 10 บาท: เราอาจจะลองไล่คำนวนทุกแบบเหมือนเดิมก็ได้ หรือเราจะบอกว่า “เมื่อกี้มีคนมาขอแลก 7 บาทไปแล้วหนิ (ใช้ 2 เหรียญ) งั้นถ้าเราเพิ่มเหรียญ 3 บาทเข้าไป 1 เหรียญ ก็จะได้มูลค่ารวม 10 บาทพอดี!”
จะเห็นว่า เป็นเพราะเรา “จำ” คำตอบของปัญหาย่อย ๆ ได้ เราจึงไม่ต้องมาเสียเวลานั่งคำนวนใหม่แต่แรกอีก และทำให้เราสามารถแก้ปัญหาได้ไวขึ้น
อย่างไรก็ตามในตัวอย่าง “การรับมูลค่าเหรียญ” จากที่เราเขียนในโพส divide and conquer ก่อนหน้า จะเห็นว่าถึงแม้ว่าเราจะแบ่งเหรียญออกเป็น 2 กอง เราไม่สามารถที่จำมูลค่าของเหรียญกองหนึ่งเพื่อนำไปใช้นับมูลค่าของเหรียญอีกกองได้ เนื่องจากว่าปัญหาย่อยนั้นแยกเป็นอิสระออกจากกัน (independent sub-problems)
ดังนั้นการ “จำ” (memorization) จะมีประโยชน์ได้ก็ต่อเมื่อปัญหาย่อยของเรามีความทับซ้อนกันเท่านั้น (overlapping sub-problems)
โดยสรุปแล้ว dynamic programming ก็คือการ “breakdown ปัญหาใหญ่ให้เป็นปัญหาย่อย ๆ ที่ทับซ้อนกัน จากนั้นใช้การจำเพื่อลดการคำนวนที่ซ้ำซ้อน เพื่อให้แก้ปัญหาได้ไวขึ้น” นั่นเอง
