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

"Those who cannot remember the past are condemned to repeat it."
Solving complex problems by breaking them into overlapping subproblems and recording their solutions. "أولئك الذين لا يتذكرون الماضي محكوم عليهم بتكراره."
حل المشكلات المعقدة عن طريق تقسيمها إلى مشاكل فرعية متداخلة (Overlapping Subproblems) وتسجيل حلولها.

Knapsack (0/1) Knapsack (0/1) Warshall's Algorithm Warshall's Algorithm Floyd's Algorithm Floyd's Algorithm Optimal BST Optimal BST

The Core Philosophy الفلسفة الأساسية

Overlapping Subproblems المشاكل الفرعية المتداخلة

Unlike Divide & Conquer (where subproblems are independent), Dynamic Programming applies when subproblems overlap. على عكس الـ Divide & Conquer (حيث تكون المشاكل الفرعية مستقلة)، تطبق Dynamic Programming عندما تتداخل المشاكل الفرعية.

Instead of solving the same subproblem again and again (recursion), we solve it once and store the result in a table. بدلاً من حل نفس المشكلة الفرعية مراراً وتكراراً (recursion)، نحلها مرة واحدة ونخزن النتيجة في جدول.

Method 1 (Top-Down): Memoization (Recursion + Table)Memoization (تكرار + جدول)
Method 2 (Bottom-Up): Tabulation (Iterative loops)Tabulation (حلقات تكرارية)

The Fibonacci Example مثال فيبوناتشي (Fibonacci)

$2^n$ Naive Recursion Naive Recursion

$n$ Dynamic Programming Dynamic Programming

Optimization Problems مشاكل التحسين (Optimization)

Coin Row Problem Coin Row Problem

Pick coins from a row to maximize sum, but you cannot pick two adjacent coins. اختر عملات من صف لتعظيم المجموع، لكن لا يمكنك اختيار عملتين متجاورتين.

$F(n) = \max(c_n + F(n-2), \quad F(n-1))$

Logic: Either pick coin $n$ (and skip $n-1$), or skip coin $n$. المنطق: إما اختيار العملة $n$ (وتخطي $n-1$)، أو تخطي العملة $n$.

Change-Making Problem Change-Making Problem

Find the minimum number of coins to make amount $n$ using denominations $d_1, d_2... d_m$. ابحث عن الحد الأدنى لعدد العملات لتكوين المبلغ $n$ باستخدام الفئات $d_1, d_2... d_m$.

$F(n) = \min_{j:n \ge d_j} \{ F(n - d_j) \} + 1$

Note: Greedy approach works for some coins (US Dollar) but fails for general cases. DP always works. النهج الجشع (Greedy) يعمل مع بعض العملات (الدولار الأمريكي) ولكنه يفشل في الحالات العامة. الـ DP يعمل دائماً.

Knapsack Problem (0/1) مسألة حقيبة الظهر (Knapsack 0/1)

Given items with weights $w_i$ and values $v_i$, maximize value in a knapsack of capacity $W$. Each item can be taken (1) or left (0). بالنظر إلى عناصر ذات أوزان $w_i$ وقيم $v_i$، قم بتعظيم القيمة في حقيبة ذات سعة $W$. كل عنصر يمكن أخذه (1) أو تركه (0).

The Recurrence Relation العلاقة التكرارية (Recurrence Relation)

$$ V[i, j] = \begin{cases} \max(V[i-1, j], \quad v_i + V[i-1, j-w_i]) & \text{if } j \ge w_i \\ V[i-1, j] & \text{if } j < w_i \end{cases} $$

$V[i, j]$: Max value using first $i$ items with capacity $j$. $V[i, j]$: القيمة القصوى باستخدام أول $i$ عناصر بسعة $j$.

Item / Cap العنصر / السعة	2	3	4	5
0 (Null) 0 (Null)	0	0	0	0
1 (w=2, v=3)	3	3	3	3
2 (w=3, v=4)	3	4	4	7

Complexity: $O(n \times W)$ (Time & Space) التعقيد: $O(n \times W)$ (الوقت والمساحة)

Graph Algorithms خوارزميات الرسم البياني (Graph)

Warshall's Algorithm Warshall's Algorithm

Transitive Closure الإغلاق المتعدي (Transitive Closure)

Finds if there is a path between every pair of vertices. يكتشف ما إذا كان هناك مسار بين كل زوج من الرؤوس (Vertices).

$R^{(k)}[i,j] = R^{(k-1)}[i,j] \lor (R^{(k-1)}[i,k] \land R^{(k-1)}[k,j])$

Uses Logical OR/AND. Complexity: $O(n^3)$. يستخدم OR/AND المنطقي. التعقيد: $O(n^3)$.

Floyd's Algorithm Floyd's Algorithm

All-Pairs Shortest Path أقصر مسار لكل الأزواج

Finds the shortest distance between every pair of vertices. يجد أقصر مسافة بين كل زوج من الرؤوس.

$D^{(k)}[i,j] = \min(D^{(k-1)}[i,j], \quad D^{(k-1)}[i,k] + D^{(k-1)}[k,j])$

Uses Min/Addition. Complexity: $O(n^3)$. يستخدم Min/Addition. التعقيد: $O(n^3)$.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Knapsack Efficiency فخ: كفاءة الـ Knapsack

"Is Knapsack 0/1 polynomial time?"
It is $O(n \cdot W)$. This looks polynomial, but $W$ is the magnitude of the capacity, not the input size. In terms of bits, it is Pseudo-Polynomial (Exponential). "هل Knapsack 0/1 يعتبر Polynomial time؟"
هو $O(n \cdot W)$. يبدو هذا كـ polynomial، لكن $W$ هو مقدار السعة، وليس حجم المدخلات. من حيث البتات، هو Pseudo-Polynomial (أسي Exponential).

TRAP: Greedy vs DP فخ: Greedy vs DP

Greedy algorithms make the local best choice. DP considers all choices. For Change-Making:
Coins: 1, 3, 4. Target: 6.
Greedy: 4 + 1 + 1 (3 coins).
DP: 3 + 3 (2 coins).
Always check if Greedy fails before using it. خوارزميات Greedy تتخذ الخيار الأفضل محلياً. الـ DP ينظر في كل الخيارات. لمسألة الصرف:
العملات: 1، 3، 4. الهدف: 6.
Greedy: 4 + 1 + 1 (3 عملات).
DP: 3 + 3 (عملتان).
تحقق دائماً مما إذا كان Greedy يفشل قبل استخدامه.

SECRET: Principle of Optimality سر: مبدأ الأمثلية (Optimality)

DP only applies if the problem satisfies the Principle of Optimality: An optimal solution to any instance must be composed of optimal solutions to its sub-instances. يطبق الـ DP فقط إذا كانت المشكلة تحقق مبدأ الأمثلية (Principle of Optimality): الحل الأمثل لأي حالة يجب أن يتكون من حلول مثلى لحالاتها الفرعية.

KEY CONCEPT: Memory Functions مفهوم أساسي: Memory Functions

Top-Down DP (Memoization) is often better than Bottom-Up if you don't need to solve all subproblems. It only solves what is required by the recursion tree. الـ Top-Down DP (Memoization) غالباً ما يكون أفضل من Bottom-Up إذا لم تكن بحاجة لحل كل المشاكل الفرعية. فهو يحل فقط ما تتطلبه شجرة العودية (Recursion Tree).