ลำดับร่วมที่ยาวที่สุด
จัดแนวสตริงสองชุดด้วยตาราง DP
ลำดับร่วมที่ยาวที่สุด เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ลำดับย่อยคืออะไร
ลำดับย่อยจะรักษาลำดับของอักขระไว้ แต่สามารถข้ามบางอักขระได้ จาก 'abcde' คุณสามารถเลือก 'ace' ได้ แต่ไม่มีทางเลือก 'aec' ได้
เป้าหมายของ LCS
เมื่อกำหนดสตริงสองชุด ลำดับย่อยร่วมที่ยาวที่สุดคือลำดับที่ยาวที่สุดซึ่งปรากฏอยู่ในทั้งสองสตริง โดยมีลำดับสัมพัทธ์เหมือนกัน
เปลี่ยนเป็นตาราง
เปรียบเทียบส่วนต้นของสตริงทั้งสอง การสร้างตารางสองมิติตามความยาวของสตริงจะเปลี่ยนปัญหานี้ให้เป็น DP บนตารางที่คุ้นเคย
กำหนดสถานะ
ให้ dp[i][j] เป็นความยาวของ LCS ระหว่างอักขระ i ตัวแรกของ A และอักขระ j ตัวแรกของ B
เมื่ออักขระตรงกัน
หาก A[i-1] เท่ากับ B[j-1] ตัวอักษรที่ตรงกันนั้นจะต่อความยาวของ LCS ให้เพิ่มขึ้น คุณบวกหนึ่งเข้ากับค่าแนวทแยง dp[i-1][j-1]
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1เมื่ออักขระต่างกัน
หากตัวอักษรต่างกัน ให้ตัดอักขระออกจากสตริงใดสตริงหนึ่งแล้วเก็บผลลัพธ์ที่ดีกว่าไว้ คุณเลือกค่าสูงสุดจากเพื่อนบ้านสองเซลล์
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])กรณีฐาน
ส่วนต้นที่ว่างเปล่าไม่มีอักขระร่วมกัน ดังนั้นความยาว LCS จึงเป็นศูนย์ แถวที่ 0 และคอลัมน์ที่ 0 จะเป็นศูนย์ทั้งหมด
dp = [[0] * (m+1) for _ in range(n+1)]เพิ่มแถวและคอลัมน์อีกหนึ่งช่อง
การกำหนดขนาดตารางเป็น n+1 คูณ m+1 จะทำให้มีขอบศูนย์เพิ่มขึ้นมาโดยไม่ต้องทำอะไร วิธีนี้ช่วยตัดการตรวจสอบขอบเขตที่น่ารำคาญตรงขอบตาราง
เติมค่าให้ครบ
วนค่า i และ j เริ่มจาก 1 ขึ้นไป แต่ละเซลล์ต้องใช้เพียงค่าด้านบน ด้านซ้าย และแนวทแยง ซึ่งถูกคำนวณแล้ว
for i in range(1, n+1):
for j in range(1, m+1):
...อ่านความยาว
ความยาว LCS ทั้งหมดจะอยู่ที่มุมตาราง คำตอบคือ dp[n][m] เมื่อเติมค่าครบทุกเซลล์แล้ว
length = dp[n][m]ความซับซ้อน
คุณเข้าถึงแต่ละเซลล์เพียงครั้งเดียว ดังนั้นการทำงานใช้เวลาและหน่วยความจำ O(n times m) ซึ่งรองรับสตริงที่ยาวไม่กี่พันอักขระได้อย่างสบาย
ตรวจสอบความเข้าใจ
อักขระปัจจุบัน A[i-1] และ B[j-1] เท่ากัน การอัปเดตใดถูกต้อง
สรุปทบทวน: LCS
สร้างตารางขนาด n+1 คูณ m+1 เมื่ออักขระตรงกันให้บวกหนึ่งเข้ากับค่าแนวทแยง มิฉะนั้นให้เลือกเพื่อนบ้านที่มีค่าสูงสุด มุมตารางจะเก็บความยาวไว้ 🔗
คำถามที่พบบ่อย
บทเรียน “ลำดับร่วมที่ยาวที่สุด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ลำดับร่วมที่ยาวที่สุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ลำดับร่วมที่ยาวที่สุด”
จัดแนวสตริงสองชุดด้วยตาราง DP คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ลำดับร่วมที่ยาวที่สุด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การนับพาธบนกริด
- ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง
- ลำดับร่วมที่ยาวที่สุด
- ระยะห่างการแก้ไขทีละขั้น