البرمجة الديناميكية (Dynamic Programming - DP)

البرمجة الديناميكية (DP) هي طريقة لحل المسائل التي:

  • تتكرر فيها نفس المسائل الفرعية عدة مرات، و
  • يمكن بناء حل المسألة الكبيرة من حلول مسائل أصغر.

الفكرة الأساسية:

لا تعيد حساب نفس الشيء مرارًا وتكرارًا. بدلًا من ذلك، خزّن (memoize) النتائج في مصفوفة أو خريطة (array أو map) وأعد استخدامها.

مثال تمهيدي: أعداد فيبوناتشي

نعرّف متتالية فيبوناتشي كالتالي:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) عندما n ≥ 2

الحل العودي الساذج (البطيء)

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

ما المشكلة هنا؟

  • fib(5) تستدعي fib(4) و fib(3)
  • fib(4) تستدعي fib(3) و fib(2)
  • الدالة fib(3) مثلًا تُستدعى مرات كثيرة مكررة

عدد الاستدعاءات يصبح أُسّيًا تقريبًا: الزمن ≈ O(2^n)، وهذا بطيء جدًّا للقيم الكبيرة من n.

إصلاحها بالتذكار (Memoization) – أسلوب من أعلى لأسفل (Top-Down DP)

ننشئ مصفوفة dp[] بحيث:

  • dp[n] تخزن قيمة fib(n) بعد حسابها مرة واحدة.

قبل حساب fib(n) نتحقق أولًا: هل dp[n] محسوبة مسبقًا أم لا.

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp;

long long fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (dp[n] != -1) return dp[n]; // already computed

    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

int main() {
    int n = 50;
    dp.assign(n + 1, -1);

    cout << "F(" << n << ") = " << fib(n) << "\n";
}

بهذا الشكل، كل fib(k) تُحسب مرة واحدة فقط، وأي استدعاء لاحق لنفس k يعيد القيمة المخزنة بدلًا من إعادة الحساب، فيصبح الزمن O(n) بدلًا من O(2^n).

إطار SRTBOT للـ DP

نستخدم إطار SRTBOT لتنظيم التفكير في أي مسألة برمجة ديناميكية.

S – State (الحالة)

ماذا تمثّل dp[i]؟

dp[i] = F(i)، أي عدد فيبوناتشي رقم i.

R – Recurrence (العلاقة العودية)

كيف نبني الحالة الكبيرة من حالات أصغر؟

dp[i] = dp[i-1] + dp[i-2] عندما i ≥ 2

T – Transitions (الانتقالات)

للوصول إلى dp[i] ننتقل من الحالتين:

  • dp[i-1]
  • و dp[i-2]

أي أن dp[i] يعتمد على هاتين الحالتين فقط.

B – Base Cases (الحالات الأساسية)

نحدد أول قيمتين:

  • dp[0] = 0
  • dp[1] = 1

بدون هذه القيم لا يمكننا بدء الحساب.

O – Order of Computation (ترتيب الحساب)

في الأسلوب من أسفل لأعلى (Bottom-Up)، نحسب القيم من الأصغر إلى الأكبر:

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

أي من 0 ← 1 ← 2 ← ... ← n.

T – Time & Space Complexity (التعقيد الزمني والذاكري)

  • الزمن: نحسب كل dp[i] مرة واحدة → O(n)
  • الذاكرة: نخزّن dp[0..n] → O(n) ويمكن تقليلها إلى O(1) إذا احتفظنا بآخر قيمتين فقط بدل المصفوفة كاملة.

أقل كلفة للوصول إلى نهاية المصفوفة

المسألة:

معطاة مصفوفة cost[0..n-1] حيث cost[i] هي الكلفة التي تدفعها عند الوقوف على الموقع i.

أنت تبدأ قبل المصفوفة وتريد الوصول إلى بعد آخر عنصر (الموقع n). من الموقع i يمكنك الانتقال إلى:

  • i + 1
  • أو i + 2

ويمكنك أن تبدأ من 0 أو من 1.

الهدف: إيجاد أقل كلفة كلية للوصول إلى الموقع n.

مثال:

cost = [1, 100, 1, 1]

Possible ways:

Start at 0:
  0 -> 2 -> n
  cost = cost[0] + cost[2] = 1 + 1 = 2

Start at 1:
  1 -> 3 -> n
  cost = 100 + 1 = 101

Answer = 2

الحل العودي الساذج

نعرّف دالة:

  • solve(i) = أقل كلفة للوصول من الموقع i إلى النهاية (الموقع n).

من i:

  • ندفع cost[i]،
  • ثم نختار الذهاب إلى i+1 أو i+2.
int n;
vector<int> cost;

int solve(int i) {
    if (i >= n) return 0;

    int take1 = solve(i + 1);
    int take2 = solve(i + 2);
    return cost[i] + min(take1, take2);
}

int main() {
    cost = {1, 100, 1, 1};
    n = cost.size();

    int ans = min(solve(0), solve(1));  // can start from 0 or 1
    cout << ans << "\n";
}

لماذا هذا الحل بطيء؟

  • solve(i) تستدعي solve(i+1) و solve(i+2).
  • نفس القيمة لـ i تُحسب مرات عديدة (مسائل فرعية متداخلة ومتكررة).
  • الزمن يصبح تقريبًا O(2^n).

إضافة التذكار (Memoization) – Top-Down DP

نستخدم مصفوفة dp[i] لتخزين أقل كلفة من الموقع i إلى النهاية:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> cost;
vector<int> dp;

int solve(int i) {
    if (i >= n) return 0;

    if (dp[i] != -1) return dp[i]; // already computed

    int take1 = solve(i + 1);
    int take2 = solve(i + 2);
    dp[i] = cost[i] + min(take1, take2);
    return dp[i];
}

int main() {
    cost = {1, 100, 1, 1};
    n = cost.size();
    dp.assign(n, -1);

    int ans = min(solve(0), solve(1));
    cout << "Minimum cost = " << ans << "\n";
}

الآن:

  • كل solve(i) تُحسب مرة واحدة فقط.
  • الزمن الكلي يصبح O(n) بدلًا من زمن أُسّي.

نسخة من أسفل لأعلى (Bottom-Up DP)

يمكننا أيضًا حل نفس المسألة بشكل تكراري من النهاية إلى البداية.

نعرّف:

dp[i] = أقل كلفة للانتقال من الموقع i إلى النهاية.

القواعد:

  • إذا كان i >= n → الكلفة 0.

  • إذا كان i < n:

    • dp[i] = cost[i] + min(dp[i+1], dp[i+2])

غالبًا نستخدم مصفوفة بحجم n+2 لتفادي مشاكل الخروج عن الحدود.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> cost = {1, 100, 1, 1};
    int n = cost.size();

    vector<int> dp(n + 2, 0); // dp[n] and dp[n+1] = 0 by default

    for (int i = n - 1; i >= 0; i--) {
        dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
    }

    int ans = min(dp[0], dp[1]); // can start from index 0 or 1
    cout << "Minimum cost = " << ans << "\n";
}

SRTBOT لمسألة أقل كلفة للوصول للنهاية

S – State (الحالة)

dp[i] = أقل كلفة إجمالية للانتقال من الموقع i حتى الموقع n (أي الوصول أو تجاوز نهاية المصفوفة).

R – Recurrence (العلاقة العودية)

من i:

  • ندفع cost[i]
  • ثم نقفز إلى i+1 أو i+2

إذًا:

dp[i] = cost[i] + min(dp[i+1], dp[i+2])

T – Transitions (الانتقالات)

من الحالة i الانتقالات الممكنة هي:

  • i → i+1
  • i → i+2

هذه هي جميع الحواف في مخطط الـ DP لهذه المسألة.

B – Base Cases (الحالات الأساسية)

نضع:

  • dp[n] = 0 (وصلنا/تجاوزنا النهاية، لا كلفة إضافية)
  • dp[n+1] = 0 (حماية عند استخدام dp[i+2] عندما i = n-1)

وفي النسخة العودية:

  • إذا كان i >= n نرجع 0.

O – Order of Computation (ترتيب الحساب)

في Bottom-Up:

  • نعالج i من n-1 نزولًا إلى 0، بحيث تكون:

    • dp[i+1] و dp[i+2] محسوبتين مسبقًا عند حساب dp[i].
for (int i = n - 1; i >= 0; i--) {
    dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
}

T – Time & Space Complexity (التعقيد الزمني والذاكري)

  • الزمن: نحسب dp[i] مرة واحدة لكل i في [0..n-1]، وكل خطوة في O(1) → المجموع O(n).
  • الذاكرة: نستخدم مصفوفة dp بحجم n+2 → O(n) (ويمكن تقليلها إلى O(1) بالاكتفاء بآخر قيمتين فقط).

الفكرة العامة للـ DP

غالبًا تظهر البرمجة الديناميكية عندما:

  1. تستطيع كتابة حل عودي (Recursive) يقوم بـ:

    • تركيب الإجابة من حلول مسائل فرعية أصغر،
    • لكنه يعيد حساب نفس المسائل الفرعية مرات عديدة.

  2. ثم تقوم بـ:

    • تعريف حالة (dp[...])،
    • اشتقاق العلاقة العودية (Recurrence)،
    • إضافة التذكار (Memoization) في أسلوب Top-Down، أو ملء جدول في أسلوب Bottom-Up.

وإطار SRTBOT يساعدك على تنظيم تفكيرك:

State → Recurrence → Transitions → Base cases → Order of computation → Time/space complexity