Dynamic Programming Without the Panic: เทคนิคเขียนโค้ด DP
เจาะลึกเทคนิคพิชิตโจทย์ Dynamic Programming ในสัมภาษณ์งานไอที เริ่มจาก Recursive ธรรมดา สู่การทำ Memoization และการสร้างตาราง Bottom-up
ภาพประกอบจากคลังภาพสต็อก ไม่ใช่ภาพจากเหตุการณ์จริง
- Dynamic Programming คือการทำ recursion ร่วมกับการจำค่า (memory)
- เริ่มต้นด้วยการเขียน recursive แบบธรรมดาก่อนแล้วค่อยใส่ cache เพื่อป้องกันความสับสน
- การนิยาม state ให้ชัดเจนใน 1 ประโยคคือกุญแจสำคัญก่อนเริ่มเขียนโค้ด
- จดจำโจทย์ 4 ตระกูลหลัก ได้แก่ knapsack, longest common subsequence, edit distance และ coin change
เมื่อพูดถึงการสัมภาษณ์งานสายเทคโนโลยี โจทย์ประเภท Dynamic Programming (DP) มักจะสร้างความตื่นกลัวให้กับผู้สมัครมากที่สุด ชื่อที่ดูยิ่งใหญ่และวิธีแก้ที่ซับซ้อนราวกับเวทมนตร์ทำให้หลายคนคิดว่าต้องอาศัยการจำเคล็ดลับเฉพาะตัว ความกลัวนี้เองที่ทำให้ผู้สมัครหลายคนสติหลุดและทำข้อสอบไม่ได้ ทั้งที่เนื้อหาจริงๆ ไม่ได้ยากอย่างที่คิด
มุมมองที่ผ่อนคลายกว่าคือการมองว่า DP เป็นเพียง recursion ที่มีระบบความจำ หากคุณสามารถเขียนฟังก์ชัน recursive แบบพื้นฐานได้ คุณก็มีพื้นฐานไปกว่าครึ่งทางแล้ว บทความนี้จะพาไปดูขั้นตอนทีละน้อยตั้งแต่การทำแบบ brute force ไปจนถึงการใช้ cache และตาราง พร้อมวิธีสังเกตโจทย์ตระกูลคลาสสิกเพื่อให้คุณคุ้นเคยกับโจทย์ใหม่ๆ ได้เร็วขึ้น
เริ่มต้นด้วยการเขียนคำตอบแบบ recursive ที่ทำงานได้ช้าแต่ถูกต้องเสียก่อน อย่าเพิ่งไปสนใจเรื่องตาราง ลองเขียนฟังก์ชันตามธรรมชาติ เช่น โจทย์การเดินขึ้นบันไดที่คุณสามารถก้าวได้ 1 หรือ 2 ขั้น จำนวนวิธีที่จะไปถึงขั้น n คือผลรวมของวิธีไปถึงขั้น n-1 และขั้น n-2 โดยมี base case คือ 1 วิธีสำหรับขั้นที่ 0 และขั้นที่ 1
ภาพประกอบจากคลังภาพสต็อก ไม่ใช่ภาพจากเหตุการณ์จริง
เมื่อลองไล่โค้ดด้วยมือสำหรับ n เท่ากับ 5 จะพบว่าฟังก์ชันเรียกซ้ำซ้อนกันหลายครั้ง เช่น การคำนวณขั้นที่ 3 ถูกเรียกซ้ำหลายหน การทำซ้ำนี้คือสัญญาณเตือนว่าปัญหาย่อยซ้อนทับกัน (overlapping subproblems) ซึ่งการใช้ cache จะช่วยแก้ปัญหานี้ได้ทันที
ในมุมมองของการพัฒนาซอฟต์แวร์ การเริ่มต้นด้วยวิธีที่ช้าแต่ถูกต้อง (Brute Force) ก่อนแล้วค่อยปรับปรุงประสิทธิภาพ เป็นแนวทางที่เรียกว่า Optimization ผิดเวลาคือรากเหง้าของความชั่วร้าย (Premature optimization is the root of all evil) การรีบเร่งเขียนโค้ดที่ซับซ้อนตั้งแต่แรกมักทำให้เกิดบั๊กที่ยากจะแกะรอย การมีโค้ดตั้งต้นที่ถูกต้องจะช่วยให้เรามีเครื่องมือไว้เทียบเคียงผลลัพธ์ของโค้ดที่เร็วกว่าได้
เมื่อเพิ่ม cache เข้าไป งานของคุณก็เกือบจะเสร็จสมบูรณ์ สร้าง dictionary หรือ array โดยใช้argument ของฟังก์ชัน recursive เป็นคีย์ ที่จุดเริ่มต้นของฟังก์ชัน ให้เช็คและคืนค่าที่บันทึกไว้ถ้ามีอยู่แล้ว และบันทึกผลลัพธ์ก่อนคืนค่า กระบวนการนี้เรียกว่า memoization ซึ่งสำหรับการสัมภาษณ์งานหลายครั้งถือว่าเป็นคำตอบที่สมบูรณ์แบบแล้ว
ให้ระบุความซับซ้อนให้ชัดเจน: แต่ละสถานะ (state) จะถูกคำนวณเพียงครั้งเดียว และการคำนวณแต่ละครั้งใช้เวลาไม่มาก ดังนั้นเวลาทั้งหมดจึงเท่ากับจำนวนสถานะคูณด้วยงานต่อสถานะ สำหรับโจทย์บันได จะใช้เวลาและพื้นที่ระดับ linear จากเดิมที่เป็น exponential
"dp of i and j means the best result when I have considered the first i items and have j left."
Sarah23
ก่อนลงมือเขียนโค้ด ให้จบประโยคนี้ให้ได้เสียก่อน: dp ของ i และ j หมายถึงผลลัพธ์ที่ดีที่สุดเมื่อพิจารณาไอเทม i ชิ้นแรกและเหลือ j ถ้าคุณเขียนประโยคนี้ไม่ได้ แปลว่าคุณยังไม่พร้อมเขียนโค้ด สถานะที่คลุมเครือคือสาเหตุหลักของโค้ด DP ที่ผิดพลาด
แปลงเป็นตาราง (Bottom-up) เฉพาะเมื่อจำเป็น วิธีนี้ช่วยเลี่ยงปัญหา recursion depth limits และช่วยประหยัดหน่วยความจำได้ โดยเติมค่าในสถานะตามลำดับที่ทราบค่าdependencies แล้ว สำหรับโจทย์ coin change ให้วนลูปจำนวนเงินจาก 1 ไปจนถึงเป้าหมายและมองย้อนกลับไปยังจำนวนเงินที่น้อยกว่า
ภาพประกอบจากคลังภาพสต็อก ไม่ใช่ภาพจากเหตุการณ์จริง
ศึกษาโจทย์ยากๆ แล้วลองแก้ด้วยตัวเอง เมื่อเจอโจทย์ที่เกินระดับความรู้ ให้ใช้เป็นกรณีศึกษา ดูว่าโจทย์ DP ยากๆ นั้นแตกย่อยออกเป็น state, transition และ base case อย่างไร จากนั้นปิดคำอธิบายแล้วลองเขียนแก้ใหม่ตั้งแต่ต้น เครื่องมืออย่าง Phantom Code AI ก็มีโหมด Deep Think ที่ช่วยวิเคราะห์อัลกอริทึมยากๆ บนเดสก์ท็อป macOS และ Windows
ที่มา: Dev.to
พบข้อมูลผิดพลาดในบทความนี้? แจ้งปัญหาบทความนี้
ความคิดเห็น
แสดงความคิดเห็น