البرمجة الديناميكية

البرمجة الديناميكية (DP) هي النمط الذي يخشاه معظم المرشحين، لكنها تتبع نهجًا منظمًا. بمجرد تعلم تحديد مسائل DP وبناء انتقالات الحالة، تصبح منهجية.

متى تستخدم DP

المسألة مرشحة لـ DP عندما تمتلك:

1. مسائل فرعية متداخلة -- نفس المسألة الفرعية تُحل مرات عديدة
2. البنية الفرعية المثلى -- الحل الأمثل يحتوي على حلول مثلى لمسائله الفرعية

اختبار سريع: إذا كان الحل التكراري سيعيد حساب نفس القيم، يمكن لـ DP المساعدة بتخزين تلك النتائج.

نهجان

النهج	كيف يعمل	المزايا	العيوب
من أعلى لأسفل (Memoization)	تكراري + تخزين النتائج	بديهي، يحل فقط المسائل الفرعية اللازمة	حمل التكرار، حد المكدس
من أسفل لأعلى (Tabulation)	تكراري، ملء الجدول من الحالات الأساسية	لا تكرار، غالبًا أكثر كفاءة	يجب تحديد الترتيب الصحيح

عملية DP من 5 خطوات

الخطوة 1: حدد أنها مسألة DP

ابحث عن: "أقل تكلفة"، "أقصى ربح"، "عدد الطرق"، "هل يمكنك الوصول..."

الخطوة 2: عرّف الحالة

ما المعلومات التي تحتاجها في كل خطوة؟ تصبح هذه مصفوفة DP الخاصة بك.

الخطوة 3: اكتب علاقة التكرار

كيف ترتبط الحالة الحالية بالحالات السابقة؟

الخطوة 4: حدد الحالات الأساسية

ما هي أصغر المسائل الفرعية التي يمكنك حلها مباشرة؟

الخطوة 5: حدد ترتيب التكرار

من أسفل لأعلى: في أي اتجاه تملأ الجدول؟

أنماط DP الأساسية

DP أحادي البعد: فيبوناتشي / صعود الدرج

# صعود الدرج: كم طريقة للوصول للخطوة n؟
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

DP أحادي البعد: سارق المنازل

# سارق المنازل: أقصى مال بدون سرقة منازل متجاورة
def rob(nums):
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    return prev1

DP ثنائي البعد: أطول سلسلة فرعية مشتركة

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

كلاسيكي: حقيبة الظهر 0/1

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]  # لا تأخذ العنصر i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                             dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

كلاسيكي: تغيير العملات

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

التعرف على أنماط DP

إشارة المسألة	فئة DP	مثال
"عدد الطرق"	DP العدّ	صعود الدرج، مسارات فريدة
"الحد الأدنى/الأقصى"	DP التحسين	تغيير العملات، سارق المنازل
"هل هو ممكن؟"	DP المنطقي	تقسيم الكلمات، تقسيم متساوٍ
"أطول/أقصر تسلسل"	DP التسلسل	LCS، LIS، مسافة التعديل
"سلسلتان نصيتان"	DP ثنائي البعد	LCS، مسافة التعديل
"عناصر بوزن/قيمة"	DP حقيبة الظهر	حقيبة 0/1، مجموع المجموعة

تحسين المساحة

العديد من مسائل DP ثنائية البعد تعتمد فقط على الصف السابق، فيمكنك تقليل المساحة من O(n*m) إلى O(n):

# مسارات فريدة: مساحة O(n) بدلاً من O(m*n)
def unique_paths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    return dp[n-1]

نصيحة للمقابلات: ابدأ بالحل التكراري، أضف التخزين المؤقت (من أعلى لأسفل)، ثم حوّل إلى من أسفل لأعلى إذا لزم الأمر. هذا يُظهر عملية تفكيرك بوضوح.

---

مع تغطية أنماط الخوارزميات، لننتقل إلى تصميم الأنظمة -- جولة مقابلة حاسمة على جميع المستويات. :::