บทที่ 24 dynamic programming เบื้องต้น
จบบทนี้ น้องจะเปลี่ยน recursion ที่ลองทุกทางแต่ช้าแบบทวีคูณ ให้เป็นโปรแกรมที่คำนวณแต่ละปัญหาย่อยครั้งเดียว ทั้งแบบจดคำตอบ (top-down) และแบบเติมตารางด้วยลูป (bottom-up) คิดสูตรเองได้ด้วยสี่ขั้น คือนิยามสถานะ หาความสัมพันธ์ กำหนดกรณีฐาน แล้วเลือกลำดับการเติมพร้อมตำแหน่งคำตอบ และประมาณเวลาได้จากจำนวนสถานะคูณงานต่อสถานะ โจทย์ที่ใช้ได้ทันทีคือแนวนับวิธีขึ้นบันได ทอนเหรียญให้น้อยที่สุด นับวิธีทอนเหรียญทั้งแบบลำดับสำคัญและไม่สำคัญ เลือกของที่ห้ามติดกัน และช่วงติดกันที่ผลรวมมากที่สุด ซึ่งเป็นโจทย์ DP ข้อแรกๆ ของค่าย 2 และ TOI ทั้งหมดนี้รวมถึงการพิมพ์คำตอบจริง ไม่ใช่แค่ตัวเลข บทที่ 25 จะใช้สี่ขั้นเดิมกับ DP สองมิติ
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 24.1 จาก recursion สู่ตาราง | ทอนเหรียญ 1 3 4 ด้วย recursion แล้วจดคำตอบ แล้วเติมตาราง ต้นไม้การเรียกที่ซ้ำ เวลาที่วัดจริง และ top-down ที่พังด้วย stack overflow |
| 24.2 วิธีคิด DP สี่ขั้น | บันไดที่มีขั้นพัง กรณีฐานที่ต้องเป็น 1 mod 1000000007 และประมาณเวลาด้วยจำนวนสถานะคูณงานต่อสถานะ |
| 24.3 ทอนเหรียญ น้อยที่สุดและนับวิธี | จำนวนที่ทำไม่ได้กับค่า INF นับแบบลำดับสำคัญกับไม่สำคัญด้วยการสลับลูป |
| 24.4 บ้านติดกันและช่วงย่อยมากสุด | เลือกหรือไม่เลือก สถานะที่จบที่ตัว i พอดี Kadane และคำตอบที่ไม่ได้อยู่ช่องสุดท้าย |
| 24.5 เก็บเส้นทางเพื่อพิมพ์คำตอบจริง | จดทางเลือกที่ชนะ เดินย้อนตาราง คำตอบที่ดีเท่ากันหลายแบบ และทำไมไม่เก็บคำตอบทั้งชุดในทุกช่อง |