Dynamic Programming คืออะไร? (Part 1)

ตอนเรียนก็เหมือนจะได้ยินบ่อยๆ ตอนสัมภาษณ์งานก็ยังจะถามอีก แล้วสรุป Dynamic Programming คืออะไรกันแน่ล่ะเนี่ย

Dynamic Programming คืออะไร?

ลองนึกภาพเล่นๆว่า เรากำลังขายของอยู่ในห้างหรืออะไรก็ได้ แล้วมีลูกค้ามาซื้อของที่เราต้องทอนเงินทั้งหมด 105 บาท

สมมติว่าเรามีแต่เหรียญ(แบงค์หมด 555) ตอนเราทอนเงิน จะหยิบเหรียญให้ยังไงดี

โดยปกติแล้วก็คงจะไม่ได้หยิบมากำนึง 105 บาทเป๊ะเลย เพราะมันทำได้ยาก แต่จะเป็นแนวๆว่าค่อยๆหยิบเหรียญ 5 บาท 10 บาทเติมๆเข้าไปจนครบ 105 บาท หรือไม่ก็หยิบกองเหรียญที่นับไว้แล้วว่านี่ 50 บาท หรือ 100 บาท แล้วเติมเหรียญที่เหลือให้ครบ

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

Dynamic Programming ก็เหมือนกัน

เพราะการหยิบเงินรวดเดียว 105 บาทหรือการแก้ปัญหา Dynamic Programming เลยมันยาก มันเลยต้องแบ่งเป็นขั้นตอนหรือปัญหาย่อยๆเพื่อให้จัดการได้ง่ายขึ้น

เอาจริงๆจะมองว่าตัวอย่างการทอนเหรียญนี้เป็นปัญหา Dynamic Programming เลยก็ได้ เพราะจริงๆมันก็ใช่ ถ้ากำหนดขอบเขตปัญหาให้ละเอียดกว่านี้หน่อย

หลักการของ Dynamic Programming

เอาจริงๆแล้ว Dynamic Programming (หลังจากนี้จะเรียกว่า DP) ก็เป็นแค่ “การเก็บค่าสถานะ” หรือจะเรียกว่าทดๆเลขไว้ก่อนก็ได้ เพื่อที่จะได้เอาค่าที่ทดๆไว้เนี่ยมาใช้แก้ปัญหาที่ต้องการ

อย่างตอนทอนเงิน เราไม่ได้แก้ปัญหาทอนเงิน 105 บาทรวดเดียว แต่เป็นการแก้ปัญหาการทอนเงิน 5 บาท 10 บาท ไปจนมันครบ 105

โดยการแก้ปัญหาแบบ DP จะมีลักษณะเด่นๆอยู่สองอย่าง

1. ปัญหาไหนที่ยังไม่ได้แก้ สามารถถูกแก้ได้ด้วยการย่อยปัญหาเป็นปัญหาอื่นที่แก้ง่ายขึ้น

   แบบที่ยกตัวอย่างไปว่าจะทอน 105 เลยทำไม คิดซะว่าทอน 100 กับ 5 บาทก็ได้

2. ปัญหาที่แก้ได้แล้ว ไม่จำเป็นต้องไปคิดซ้ำ เพราะคำตอบมันเหมือนเดิม อย่างถ้าถามว่าทอนเงิน 100 บาทต้องใช้เหรียญ 5 กี่เหรียญ ถ้าเรารู้อยู่แล้วว่าตอบเท่าไหร่ ก็ไม่ต้องไปคิดซ้ำแล้ว

ทีนี้เราได้แตะๆไปนิดนึงว่าการทอนเหรียญมันก็เป็น DP ถ้ากำหนดขอบเขตปัญหาไว้หน่อย ขอบเขตที่ว่าเนี่ยเราจะเรียกว่า State หรือ DP State แล้วแต่เลย ซึ่งจะมาดูใน section หน้าว่ามันมีไว้ทำอะไร

กำหนด State ของ Dynamic Programming

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

ทีนี้เราจะ เก็บ/ทด อะไรในนั้นก็ได้ แต่หลักๆ ที่เราอยากได้มักจะเป็น

1. เก็บค่าที่ดีที่สุด (น้อยสุดหรือมากสุด) จากนิยามปัญหาที่เราตั้งไว้

2. หรือจำนวนวิธีที่เป็นไปได้จากการทำอะไรบางอย่าง

3. เก็บแค่ว่าทำอะไรสักอย่างได้ไหม (แบบ True หรือ False เลย)

ซึ่งการเก็บค่าเหล่านี้ส่วนใหญ่จะทำบนอาเรย์ที่อาจจะมีได้มากกว่า 1 มิติ เพื่อเก็บลักษณะสำคัญในตอนนั้นๆ (เราเรียกว่า State)

State คืออะไรนะ?

มันก็ไม่ได้มีอะไรมาก แค่เหมือนเป็นการอธิบายสภาพปัญหา ณ ตอนนั้น ซึ่งยิ่งอธิบายละเอียดมากเท่าไหร่ก็ยิ่งดีมากขึ้นเท่านั้น

เช่น ถ้าเราจะทอนเงินโดยใช้เหรียญน้อยที่สุด คำถามถัดมาที่ต้องคิดคือ

1. เราต้องทอนเงินเท่าไหร่
2. มีเหรียญให้ใช้ได้กี่ประเภท
3. แล้วอาจจะต้องคิดเพิ่มว่า มีเหรียญแต่ละประเภทอย่างละเท่าไหร่ด้วย

เพื่อความง่าย สมมติให้ว่ามีเหรียญไม่จำกัดจำนวน แล้วก็ถามแค่ว่าทอนได้/ไม่ได้ละกัน เราก็จะเหลือ state แค่ 2 อย่างที่ต้องคิด คือ จะทอนเงินเท่าไหร่ และ ใช้เหรียญกี่ประเภท

ซึ่งเราก็สามารถสร้าง อาเรย์ $dp$ มาเก็บ state ได้ โดยให้ $dp[i][j]$ คือการทอนเงิน $i$ บาท (state 1) โดยใช้เหรียญทั้งหมด $j$ ประเภท (state 2) แล้วถ้าต้องการเก็บแค่ว่าทอนได้/ไม่ได้จะมีค่าเป็น

อะไรประมาณนั้น

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