نمط البرمجة الديناميكية للفواصل وترتيب الملء
عرّف حالة البرمجة الديناميكية للفواصل dp[i][j]، واشرح سبب ضرورة ملء الفواصل بترتيب متزايد حسب الطول، وتتّبع النمط على مسألة ضرب سلسلة المصفوفات.
نمط البرمجة الديناميكية للفواصل وترتيب الملء درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما المقصود بالبرمجة الديناميكية على الفترات؟
البرمجة الديناميكية على الفترات هي نمط من أنماط البرمجة الديناميكية، حيث تمثل الحالة dp[i][j] الحل الأمثل للمسألة الفرعية الممتدة من الفهرس i إلى الفهرس j. تتمثل الفكرة الأساسية في حل الفترات الأصغر أولًا ثم البناء عليها للوصول إلى النطاق الكامل. يناسب هذا النمط مسائل مثل ضرب سلسلة المصفوفات، وتقسيم المتناظرات، وتفجير البالونات، حيث تمثل حدود المسألة الفرعية الطرفين الأيسر والأيمن لنطاق ما.
تعريف الحالة والحالات الأساسية
في البرمجة الديناميكية على الفترات، تكون الحالة هي dp[i][j] حيث i <= j. أما الحالات الأساسية فهي الفترات ذات العنصر الواحد: dp[i][i]. ويكون حل هذه الحالات بديهيًا — فعلى سبيل المثال، لا تتطلب مصفوفة واحدة أي تكلفة للضرب. وغالبًا ما تكون للفترات ذات العنصرين dp[i][i+1] إجابات بسيطة أيضًا. نملأ الجدول بأطوال فترات متزايدة، بدءًا من الطول 1 وصولًا إلى n.
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervalsترتيب الملء: الأطوال المتزايدة
التفصيل الحاسم في البرمجة الديناميكية على الفترات هو ترتيب الملء. يجب أن نحسب جميع الفترات ذات الطول L قبل حساب الفترات ذات الطول L+1، لأن الفترة الأطول تعتمد على فترات فرعية أقصر. تكرّر الحلقة الخارجية طول الفترة من 2 إلى n، وتحدد الحلقة الوسطى الحد الأيسر i، ثم نشتق الحد الأيمن من خلال j = i + L - 1.
n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for length in range(2, n + 1): # interval length
for i in range(n - length + 1): # left boundary
j = i + length - 1 # right boundary
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])إعداد ضرب سلسلة المصفوفات
مسألة البرمجة الديناميكية على الفترات الكلاسيكية هي ضرب سلسلة المصفوفات: عند إعطائنا مصفوفات ذات أبعاد dims[0..n]، نجد الحد الأدنى لعدد عمليات الضرب العددية اللازمة لحساب حاصل الضرب. يتطلب ضرب المصفوفة A(p×q) في المصفوفة B(q×r) عددًا من العمليات يساوي p*q*r. وتمثل dp[i][j] الحد الأدنى لتكلفة ضرب المصفوفات من i إلى j. وتحدد نقطة التقسيم k الموضع الذي تُقسَّم عنده السلسلة إلى سلسلتين فرعيتين.
def matrix_chain_order(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
print(matrix_chain_order([10, 30, 5, 60])) # 4500تتبّع جدول DP
لنتتبّع مثال سلسلة المصفوفات ذي الأبعاد [10, 30, 5, 60]، والذي يمثل ثلاث مصفوفات: A(10×30) وB(30×5) وC(5×60). بالنسبة إلى dp[0][2]، نجرّب التقسيم عند k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000، وعند k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. لذلك تكون dp[0][2] = 4500، وذلك بضرب AB أولًا.
لماذا ينجح ترتيب الملء هذا
عند حساب dp[i][j]، نرجع إلى dp[i][k] وdp[k+1][j] لكل k في [i, j-1]. ويكون طول كلتا الفترتين الفرعيتين أصغر تمامًا من طول [i, j]. ومن خلال التكرار على الأطوال من الأصغر إلى الأكبر، تُحسَب جميع الفترات الفرعية المطلوبة قبل الحاجة إليها. هذه هي حجة الصحة الأساسية لترتيب ملء البرمجة الديناميكية على الفترات — فالفترات الأقصر تكون دائمًا تبعيات للفترات الأطول.
البرمجة الديناميكية على الفترات من أعلى إلى أسفل مع الحفظ
بدلًا من ذلك، يمكن تنفيذ البرمجة الديناميكية على الفترات من أعلى إلى أسفل مع الحفظ. نكتب دالة تكرارية solve(i, j) تعيد التكلفة المثلى للفترة [i, j]، ونخزّن النتائج في قاموس. ويتولى الاستدعاء التكراري ترتيب الملء تلقائيًا. غالبًا ما يكون الأسلوب من أعلى إلى أسفل أسهل في الفهم، لكنه قد يضيف تكلفة استدعاءات الدوال؛ أما الأسلوب من أسفل إلى أعلى فهو أسرع عمليًا للمدخلات الكبيرة.
from functools import lru_cache
def matrix_chain_memo(dims):
n = len(dims) - 1
@lru_cache(maxsize=None)
def solve(i, j):
if i == j:
return 0
return min(
solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
for k in range(i, j)
)
return solve(0, n-1)
print(matrix_chain_memo([10, 30, 5, 60])) # 4500التعقيد الزمني وتعقيد المساحة
تحتوي البرمجة الديناميكية على الفترات على O(n²) من الحالات (جميع الأزواج (i, j))، وتكرّر كل حالة على O(n) من نقاط التقسيم، ما ينتج عنه زمن إجمالي قدره O(n³). وتبلغ المساحة O(n²) لجدول DP. وفي حالة ضرب سلسلة مكوّنة من 100 مصفوفة، يعادل ذلك 1,000,000 عملية، وهو عدد مناسب جدًا. يظهر هذا النمط في العديد من مسائل LeetCode الصعبة، ويفضّله المحاورون في مقابلات FAANG بسبب بنيته غير البديهية.
إعادة بناء الحل الأمثل
لإعادة بناء التجميع الفعلي بين الأقواس (وليس التكلفة فقط)، خزّنوا جدولًا منفصلًا باسم split[i][j] يسجّل قيمة k التي حققت الحد الأدنى في كل حالة. ثم اقرأوا نقاط التقسيم تكراريًا: تطبع reconstruct(i, j) التجميع الأمثل من خلال الاستدعاء التكراري على [i, split[i][j]] و[split[i][j]+1, j]. تنطبق هذه التقنية على جميع مسائل البرمجة الديناميكية على الفترات.
def matrix_chain_with_split(dims):
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
split = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp[0][n-1], splitقالب لأي مسألة برمجة ديناميكية على الفترات
يتكوّن القالب العام للبرمجة الديناميكية على الفترات من ثلاثة أجزاء: (1) تهيئة الحالات الأساسية للعناصر المفردة، (2) التكرار على الأطوال المتزايدة، ثم التكرار لكل طول على الحدود اليسرى الصالحة وحساب الحد الأيمن، و(3) التكرار داخل كل فترة على جميع نقاط التقسيم وتطبيق علاقة التكرار الخاصة بالمسألة. الشيء الوحيد الذي يتغير بين المسائل هو صيغة علاقة التكرار داخل الحلقة الداخلية.
def interval_dp_template(n, base_cost, split_cost):
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = base_cost(i) # problem-specific base case
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
# problem-specific recurrence
candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
dp[i][j] = min(dp[i][j], candidate)
return dp[0][n-1]مسائل شائعة في البرمجة الديناميكية على الفترات
تشمل المسائل التي تستخدم البرمجة الديناميكية على الفترات: ضرب سلسلة المصفوفات (تقليل العمليات)، وتفجير البالونات (تعظيم العملات)، والطابع الغريب (تقليل عمليات الطباعة)، والتثليث ذي أقل مجموع نقاط لمضلع، وتقسيم المتناظرات II. تستخدم كل مسألة هيكل ترتيب الملء نفسه، لكنها تختلف في علاقات التكرار. تعرّفوا على هذا النمط عندما تطلب المسألة قيمة مثلى لنطاق أو سلسلة يمكن تقسيمها عند أي نقطة داخلية.
اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلّمتم في هذا الدرس أن البرمجة الديناميكية على الفترات تستخدم dp[i][j] لتمثيل الحل الأمثل على نطاق، وأن ترتيب الملء يجب أن يعتمد على أطوال فترات متزايدة كي تُحسَب الفترات الفرعية أولًا، وأن القالب العام يستغرق زمنًا قدره O(n³) ومساحة قدرها O(n²). ننتقل بعد ذلك إلى استكشاف أطول متتالية جزئية متناظرة وأطول سلسلة فرعية متناظرة باستخدام هذا النمط نفسه.
الأسئلة الشائعة
هل درس «نمط البرمجة الديناميكية للفواصل وترتيب الملء» مجاني؟
نعم — نص درس «نمط البرمجة الديناميكية للفواصل وترتيب الملء» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «نمط البرمجة الديناميكية للفواصل وترتيب الملء»؟
عرّف حالة البرمجة الديناميكية للفواصل dp[i][j]، واشرح سبب ضرورة ملء الفواصل بترتيب متزايد حسب الطول، وتتّبع النمط على مسألة ضرب سلسلة المصفوفات. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «نمط البرمجة الديناميكية للفواصل وترتيب الملء»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- نمط البرمجة الديناميكية للفواصل وترتيب الملء
- أطول تتابع جزئي وسلسلة فرعية متناظرة
- تقسيم السلسلة إلى مقاطع متناظرة II
- تفجير البالونات: البرمجة الديناميكية العكسية للفواصل