أطول تتابع مشترك
محاذاة سلسلتين باستخدام جدول برمجة ديناميكية
أطول تتابع مشترك درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 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عندما تختلف المحارف
إذا اختلف المحرفان، احذف محرفًا واحدًا من إحدى السلسلتين واحتفظ بالنتيجة الأفضل. خذ قيمة max للجارين.
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 by 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 by m+1: عند التطابق أضف واحدًا إلى القطر، وإلا فخذ قيمة الجار الأكبر. تحتوي الزاوية على الطول. 🔗
الأسئلة الشائعة
هل درس «أطول تتابع مشترك» مجاني؟
نعم — نص درس «أطول تتابع مشترك» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أطول تتابع مشترك»؟
محاذاة سلسلتين باستخدام جدول برمجة ديناميكية تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «أطول تتابع مشترك»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.