บทที่ 25 dynamic programming แบบคลาสสิก
บทที่ 24 สอนวิธีคิด DP สี่ขั้นกับโจทย์ที่สถานะมีมิติเดียว บทนี้เอาวิธีคิดเดิมไปใช้กับโจทย์ DP ที่เป็นแม่แบบของโจทย์ค่าย 2 และ TOI เกือบทุกข้อ knapsack เลือกของให้คุ้มภายใต้ขีดจำกัด LIS หาลำดับย่อยที่เพิ่มขึ้นยาวที่สุดด้วย O(N log N) LCS กับ edit distance เทียบสตริงสองตัวด้วยตารางสองมิติ DP บนตารางที่เดินขวากับลง DP ช่วงสำหรับโจทย์ที่ลำดับการทำมีผลกับต้นทุน และ DP บน bitmask สำหรับโจทย์ที่ N เล็กแต่ต้องเลือกลำดับ จบบทนี้น้องจะเห็นโจทย์ใหม่แล้วจำได้ว่าคล้ายแม่แบบตัวไหน ย้อนรอยพิมพ์คำตอบจริงได้ และลดหน่วยความจำเหลือแถวเดียวหรือสองแถวเมื่อตารางใหญ่เกิน
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 25.1 0/1 knapsack และ unbounded knapsack | ตารางสองมิติ ย้อนรอยหาของที่หยิบ ลดเหลือแถวเดียวที่ต้องวนถอยหลัง เห็นว่าวนเดินหน้าคือ unbounded knapsack และกับดักตารางใหญ่ใน main |
| 25.2 LIS ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด | DP แบบ O(N2) อาเรย์ tails กับ lower_bound แบบ O(N log N) พิมพ์ลำดับจริง และเพิ่มขึ้นกับไม่ลดลงต่างกันที่ฟังก์ชันเดียว |
| 25.3 LCS และ edit distance | ตารางสองมิติที่เติมทีละช่อง ย้อนรอยจากมุมตาราง เก็บแค่สองแถว และกับดัก s[i] กับ s[i - 1] |
| 25.4 DP บนตาราง | นับทางเดิน มีสิ่งกีดขวางกับ mod เส้นทางที่เก็บของได้มากสุด เหลือแถวเดียว และกับดักที่ขอบตาราง |
| 25.5 DP ช่วงและ DP บน bitmask | ตัดไม้ให้ต้นทุนน้อยสุดด้วยการเติมตามความยาวช่วง คูณเมทริกซ์ลูกโซ่ และเส้นทางส่งของด้วย bitmask |