ระยะห่างการแก้ไขทีละขั้น

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

ในการแก้ไขแต่ละครั้ง คุณสามารถแทรก ลบ หรือแทนที่อักขระหนึ่งตัวได้ ในปัญหามาตรฐาน การดำเนินการแต่ละแบบมีต้นทุนเท่ากับหนึ่งพอดี

ให้ dp[i][j] เป็นจำนวนการแก้ไขเพื่อเปลี่ยนอักขระ i ตัวแรกของ A ให้เป็นอักขระ j ตัวแรกของ B

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

เมื่ออักขระต่างกัน ให้เลือกเพื่อนบ้านที่มีต้นทุนต่ำที่สุดแล้วบวกการแก้ไขอีกหนึ่งครั้ง การเลือกค่าต่ำสุดบวกหนึ่งครอบคลุมการดำเนินการทั้งสามแบบ

เซลล์ด้านบนหมายถึงการลบ เซลล์ด้านซ้ายหมายถึงการแทรก และเซลล์แนวทแยงหมายถึงการแทนที่ การหาค่าต่ำสุดจะเลือกทางที่มีต้นทุนต่ำที่สุด

การเปลี่ยนสตริงที่มีความยาว i ให้เป็นสตริงว่างต้องลบ i ครั้ง ดังนั้นให้เติมแถวและคอลัมน์แรกด้วย 0, 1, 2 ไปเรื่อย ๆ

ใช้ตารางขนาด n+1 คูณ m+1 เพื่อให้ส่วนต้นที่ว่างเปล่ามีแถวและคอลัมน์เป็นของตัวเอง การเติมช่องว่างนี้ทำให้ลูปเรียบง่าย

วนค่า i และ j เพิ่มขึ้นจาก 1 ทุกเซลล์ขึ้นอยู่กับเพื่อนบ้านด้านบน ด้านซ้าย และแนวทแยงที่เติมค่าแล้วเท่านั้น

จำนวนการแก้ไขที่น้อยที่สุดจะไปอยู่ที่มุมตาราง คำตอบของคุณคือ dp[n][m] หลังจากเติมตารางเสร็จสมบูรณ์

วิธีนี้ใช้เวลา O(n times m) งานจริงอาจกำหนดต้นทุนของการดำเนินการแต่ละแบบแตกต่างกัน แต่สมการเวียนเกิดเดิมยังคงใช้ได้

ถ้าตรงกัน ให้ส่งต่อค่าแนวทแยง หากไม่ตรงกัน ให้ใช้หนึ่งบวกค่าต่ำสุดของเพื่อนบ้านทั้งสาม กำหนดค่าขอบตาราง แล้วอ่านค่าdp[n][m] ✏️