กำหนดสถานะและการเปลี่ยนสถานะ

DP ทุกแบบเริ่มจากการกำหนดสถานะว่า dp[i] แทนอะไร เขียนประโยคนี้ให้ถูกต้อง แล้วส่วนที่เหลือจะตามมา

เขียนความหมายออกมาเป็นคำพูดว่า dp[i] = คำตอบสำหรับรายการ i รายการแรก การนิยามสถานะที่คลุมเครือนำไปสู่สมการเวียนเกิดที่มีข้อผิดพลาด

การเปลี่ยนสถานะบอกว่า dp[i] สร้างจากสถานะก่อนหน้าอย่างไร นี่คือสมการเวียนเกิดซึ่งเป็นแกนกลางของวิธีแก้ปัญหา

กรณีฐานคือสถานะที่เล็กที่สุดซึ่งคุณทราบคำตอบได้โดยตรง หากจุดยึดไม่ถูกต้อง ค่าทั้งหมดในภายหลังก็จะผิดเพี้ยน

แต่ละสถานะต้องถูกเติมหลังจากสถานะที่สถานะนั้นพึ่งพาอยู่ กฎการพึ่งพานี้จะกำหนดทิศทางของลูป

กำหนดว่าช่องใดเก็บผลลัพธ์สุดท้าย โดยมากจะเป็น dp[n] แต่บางครั้งอาจเป็นค่าสูงสุดของทั้งตาราง

จำนวนสถานะที่แตกต่างกันจะกำหนดงบเวลาการทำงานของคุณ DP แบบหนึ่งมิติบนรายการ n รายการมีสถานะ O(n) สถานะที่ต้องเติม

เวลารวมเท่ากับจำนวนสถานะคูณด้วยงานต่อการเปลี่ยนสถานะ หากการเปลี่ยนสถานะใช้เวลา O(n) ภายในสถานะจำนวน n สถานะ จะได้เวลา O(n กำลังสอง)

หากดัชนีเดียวไม่สามารถอธิบายสถานการณ์ได้ ให้เพิ่มอีกดัชนีหนึ่ง มิติที่สองจะเปลี่ยน dp[i] เป็น dp[i][j]

หากต้องการกู้คืนคำตอบจริง ให้บันทึกว่า การเปลี่ยนสถานะ ใดเป็นผู้ชนะในแต่ละสถานะ จากนั้นย้อนกลับจากคำตอบ

สถานะ การเปลี่ยนสถานะ กรณีฐาน ลำดับ และคำตอบ กำหนดทั้งห้าสิ่งนี้ให้ชัดเจน แล้วความสัมพันธ์เวียนเกิดของ DP แทบทุกแบบก็จะลงตัว

คุณกำลังออกแบบ DP อยู่ dp[i] แทนอะไร

ตอนนี้คุณสามารถกำหนด สถานะ เขียนการเปลี่ยนสถานะ ตั้งกรณีฐาน และระบุตำแหน่งคำตอบได้แล้ว โครงร่างนี้เปลี่ยน DP จากการคาดเดาให้กลายเป็นขั้นตอนที่ทำตามได้