DP مش مسائل صعبة، DP طريقة تفكير
الـ Dynamic Programming = recursion + ذاكرة. لو المسألة الكبيرة بتتحل من مسائل أصغر من نفس النوع (optimal substructure)، والمسائل الأصغر دي بتتكرر كتير (overlapping subproblems)، يبقى بدل ما تحسب نفس الحاجة ألف مرة، تحسبها مرة وتخزنها. كل الصعوبة في خطوة واحدة: تعريف الـ state. بعد كده الكود سهل.
| الإشارة في المسألة | غالبًا DP |
|---|---|
| «كام طريقة…؟» (counting) | نعم — جمع على الاختيارات |
| «أقل/أكبر تكلفة/طول/ربح» مع اختيارات بتأثر على اللي بعدها | نعم — min/max على الاختيارات |
| «هل ممكن…؟» مع تجربة تركيبات | نعم — OR على الاختيارات |
| Greedy بيبان صح بس عندك مثال مضاد | نعم غالبًا |
| محتاج كل الحلول نفسها (مش عددها) | لأ — backtracking |
إطار الـ 5 أسئلة: اكتب المعادلة قبل الكود
- الـ state: إيه أقل معلومات محتاجها عشان أوصف «مسألة فرعية»؟ اكتبها كـ
dp[i]أوdp[i][j]بجملة عربي كاملة: «dp[i] = أقل تكلفة للوصول للسلمة i». - الـ transition: لو أنا في الـ state دي، إيه آخر قرار ممكن أكون أخدته؟ الإجابة بتديك المعادلة:
dp[i] = cost[i] + min(dp[i−1], dp[i−2]). - الـ base cases: أصغر مسائل إجابتها معروفة من غير حساب.
- ترتيب الحساب: كل state لازم تتحسب بعد الـ states اللي بتعتمد عليها (من الصغير للكبير، أو أي topological order).
- الإجابة فين؟
dp[n]؟ ولاmax(dp)؟ ولاdp[0][n−1]؟
لو مش قادر تكتب الجملة العربي لتعريف dp[i]، ما تكتبش كود. أغلب الـ bugs في الـ DP جاية من state غامضة: «dp[i] = الإجابة لحد i» — يعني إيه «لحد»؟ شامل i ولا لأ؟ لازم ينتهي عند i ولا ممكن قبله؟
Top-down مقابل bottom-up
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| الكتابة | الأقرب للمعادلة؛ recursion + cache | loops بترتيب صريح |
| بيحسب | الـ states اللي محتاجها بس | كل الـ states |
| المخاطر | stack overflow مع عمق كبير (10⁵) | لازم تعرف ترتيب الحساب |
| تقليل المساحة | صعب | سهل (rolling array) |
في الإنترفيو: ابدأ بالـ top-down عشان توصل للصح بسرعة، وبعدين حوّل لـ bottom-up لو المحاور سأل عن المساحة أو العمق.
1D DP: House Robber و Climbing Stairs و Decode Ways
House Robber: مسار التفكير
المسألة: بيوت فيها فلوس nums[i]، ما ينفعش تاخد من بيتين جنب بعض. أكبر مجموع؟
- Greedy «خد الأكبر» بيفشل:
[2, 7, 9, 3, 1]— الأمثل 2+9+1 = 12. - State:
dp[i]= أكبر مجموع من البيوت 0..i (مش لازم آخد i). - آخر قرار عند i: يا آخده (فما آخدش i−1):
nums[i] + dp[i−2]، يا ما آخدوش:dp[i−1]. dp[i] = max(dp[i−1], nums[i] + dp[i−2])، base:dp[0] = nums[0]،dp[1] = max(nums[0], nums[1]).- كل state بتعتمد على اتنين قبلها بس ← متغيرين بدل array: O(1) مساحة.
public static int Rob(int[] nums)
{
int prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]; empty prefix = 0 removes special cases
foreach (var x in nums)
{
int cur = Math.Max(prev1, x + prev2);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
// Trace [2,7,9,3,1]: 2, 7, 11, 11, 12 -> 12Decode Ways: counting DP
«226» ممكن يتفك كـ (2,2,6) أو (22,6) أو (2,26) = 3. dp[i] = عدد طرق فك أول i حرف. آخر خطوة: يا آخر رقم لوحده (لو مش '0') ← dp[i−1]، يا آخر رقمين مع بعض (لو بين 10 و26) ← dp[i−2]. ده جمع مش max — نفس الإطار، عملية مختلفة.
public static int NumDecodings(string s)
{
if (s.Length == 0 || s[0] == '0') return 0;
int prev2 = 1, prev1 = 1; // dp[0] = 1 (empty string), dp[1] = 1
for (int i = 2; i <= s.Length; i++)
{
int cur = 0;
if (s[i - 1] != '0') cur += prev1; // single digit
int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
if (two is >= 10 and <= 26) cur += prev2; // two digits
(prev2, prev1) = (prev1, cur);
}
return prev1;
}Grid DP: Unique Paths و Minimum Path Sum
dp[r][c] = أقل مجموع للوصول للخلية (r, c) بالتحرك يمين أو تحت بس. آخر خطوة جت من فوق أو من الشمال: dp[r][c] = grid[r][c] + min(dp[r−1][c], dp[r][c−1]). الصف الأول والعمود الأول ليهم طريق واحد بس.
public static int MinPathSum(int[][] g)
{
int cols = g[0].Length;
var dp = new int[cols];
for (int r = 0; r < g.Length; r++)
for (int c = 0; c < cols; c++)
{
if (r == 0 && c == 0) dp[c] = g[0][0];
else if (r == 0) dp[c] = dp[c - 1] + g[r][c]; // only from the left
else if (c == 0) dp[c] = dp[c] + g[r][c]; // only from above (old dp[c])
else dp[c] = g[r][c] + Math.Min(dp[c], dp[c - 1]); // dp[c] = above, dp[c-1] = left (already updated)
}
return dp[cols - 1];
}ليه صف واحد كفاية؟ وانت بتحسب الصف r، dp[c] لسه فيه قيمة الصف r−1 (فوق)، و dp[c−1] اتحدّث للصف r (شمال). ده نمط «rolling array» بتشوفه في كل grid DP.
Knapsack: 0/1 مقابل unbounded
0/1: عناصر ليها وزن وقيمة، شنطة سعتها W، كل عنصر مرة واحدة بالكتير. dp[i][w] = أكبر قيمة باستخدام أول i عنصر وسعة w. القرار عند العنصر i: ما آخدوش ← dp[i−1][w]، آخده (لو وزنه ≤ w) ← value[i] + dp[i−1][w − weight[i]].
public static int Knapsack01(int[] weight, int[] value, int W)
{
var dp = new int[W + 1];
for (int i = 0; i < weight.Length; i++)
for (int w = W; w >= weight[i]; w--) // downward: dp[w - weight] is still "without item i"
dp[w] = Math.Max(dp[w], value[i] + dp[w - weight[i]]);
return dp[W];
}| النوع | اتجاه loop السعة (1D) | ليه | أمثلة |
|---|---|---|---|
| 0/1 | تنازلي | عشان ما تستخدمش نفس العنصر مرتين في نفس الدورة | Partition Equal Subset Sum، Target Sum |
| Unbounded | تصاعدي | استخدام العنصر تاني مسموح | Coin Change، Rod Cutting |
تطبيق حقيقي: اختيار chunks للـ context window: كل chunk ليه «طول بالـ tokens» (وزن) و«relevance score» (قيمة)، والسعة = الـ token budget. ده 0/1 knapsack. عمليًا الـ greedy بالـ score/token بيقرّب كويس وأسرع، والـ DP بيديك الأمثل لما الأعداد صغيرة — وده نقاش trade-off ممتاز في إنترفيو AI engineer.
التعقيد: O(n × W) — «pseudo-polynomial» لأنه بيعتمد على قيمة W مش عدد الأرقام. لو W = 10⁹ مش هينفع.
String DP: LCS و Edit Distance
مع سلسلتين، الـ state الطبيعية: dp[i][j] = الإجابة لأول i حرف من A وأول j حرف من B.
Longest Common Subsequence
لو A[i−1] == B[j−1]: الحرف ده جزء من الـ LCS ← dp[i−1][j−1] + 1. غير كده: اشيل حرف من A أو من B ← max(dp[i−1][j], dp[i][j−1]).
Edit Distance (Levenshtein)
public static int EditDistance(string a, string b)
{
var prev = new int[b.Length + 1];
var cur = new int[b.Length + 1];
for (int j = 0; j <= b.Length; j++) prev[j] = j; // "" -> b[..j] needs j inserts
for (int i = 1; i <= a.Length; i++)
{
cur[0] = i; // a[..i] -> "" needs i deletes
for (int j = 1; j <= b.Length; j++)
{
int replace = prev[j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1);
cur[j] = Math.Min(replace, Math.Min(prev[j] + 1, cur[j - 1] + 1));
}
(prev, cur) = (cur, prev);
}
return prev[b.Length];
}الربط: نفس الخوارزمية على كلمات بدل حروف = WER اللي في Speech & Audio، و LCS على الأسطر = git diff.
رجّع الحل نفسه مش القيمة بس
المحاور كتير بيسأل بعد ما تحسب الرقم: «طب أنهي العناصر؟». الحل: احتفظ بالجدول الكامل (مش النسخة المضغوطة) وامشي بالعكس من الإجابة، وفي كل خلية اسأل «القيمة دي جت منين؟».
public static string Lcs(string a, string b)
{
var dp = new int[a.Length + 1, b.Length + 1];
for (int i = 1; i <= a.Length; i++)
for (int j = 1; j <= b.Length; j++)
dp[i, j] = a[i - 1] == b[j - 1] ? dp[i - 1, j - 1] + 1 : Math.Max(dp[i - 1, j], dp[i, j - 1]);
var sb = new StringBuilder();
for (int i = a.Length, j = b.Length; i > 0 && j > 0;)
{
if (a[i - 1] == b[j - 1]) { sb.Insert(0, a[i - 1]); i--; j--; } // came diagonally
else if (dp[i - 1, j] >= dp[i, j - 1]) i--; // came from above
else j--; // came from the left
}
return sb.ToString();
}
// Lcs("ABCBDAB", "BDCABA") -> "BCBA" (one of the valid answers, length 4)Interval DP و State design متقدم
لما المسألة عن «قطعة متصلة [i..j]» والقرار هو «أقسمها فين؟»، الـ state بتبقى dp[i][j] والترتيب حسب طول الفترة (القصيرة الأول).
Longest Palindromic Subsequence: dp[i][j] = أطول palindrome subsequence في s[i..j]. لو s[i] == s[j] ← 2 + dp[i+1][j−1]، غير كده max(dp[i+1][j], dp[i][j−1]). الحساب بالطول من 1 لـ n.
لما الـ state محتاجة أكتر من index
| المسألة | الـ state | ليه البعد الإضافي |
|---|---|---|
| Best Time to Buy/Sell Stock with cooldown | dp[i][holding?] | القرار المسموح بيعتمد على إنك ماسك سهم ولا لأ |
| Paint House (لون مختلف عن الجار) | dp[i][color] | محتاج تعرف لون البيت اللي قبله |
| Travelling salesman (n ≤ 16) | dp[mask][last] | مين اتزار (bitmask) وانت فين دلوقتي |
| Viterbi (HMM / CRF decoding) | dp[t][state] | أحسن مسار ينتهي بالحالة دي عند الوقت t |
قاعدة الـ state design: اسأل «إيه اللي محتاج أفتكره عن الماضي عشان أقرر الخطوة الجاية صح؟». أي حاجة أقل من كده = إجابات غلط، أي حاجة أكتر = حجم ووقت زيادة.
DP في الشغل الحقيقي
- Fuzzy matching: بحث أسماء منتجات أو عملاء بأخطاء إملائية (edit distance مع حد أقصى بيوقف الحساب بدري).
- Diff و merge: LCS على الأسطر، وده اللي جوه أدوات الـ code review.
- Speech/NLP: WER (edit distance على كلمات)، CTC decoding، Viterbi.
- Text layout: تقسيم الأسطر بأقل «قبح» (Knuth–Plass) — DP على مواضع الكسر.
- Resource allocation: توزيع budget محدود على حملات/tenants بقيم مختلفة (knapsack-style).
DP كـ state machine: مسائل الأسهم
مسائل «Best Time to Buy and Sell Stock» بتعلّمك أهم مهارة في الـ DP: لما القرار المسموح بيعتمد على «حالتك»، خلي الحالة جزء من الـ state. مع cooldown (لازم تستنى يوم بعد البيع):
public static int MaxProfit(int[] prices)
{
int free = 0, hold = int.MinValue / 2, cool = 0; // best profit ending today in each state
foreach (var p in prices)
{
int newFree = Math.Max(free, cool); // rest, or cooldown ends
int newHold = Math.Max(hold, free - p); // keep holding, or buy today
int newCool = hold + p; // sell today
(free, hold, cool) = (newFree, newHold, newCool);
}
return Math.Max(free, cool);
}
// [1,2,3,0,2] -> 3 (buy 1, sell 2, cooldown, buy 0, sell 2)نفس الطريقة بتحل «مع رسوم»، «بحد أقصى k عمليات» (ضيف بعد k للـ state)، وأي مسألة فيها «modes» بتتغير.
Combinations مقابل permutations: ترتيب الـ loops بيغير الإجابة
Coin Change II: عدد الطرق لعمل مبلغ بعملات غير محدودة. لو الـ loop الخارجي على العملات والداخلي على المبلغ، بتعد combinations (1+2 و2+1 نفس الطريقة). لو العكس (المبلغ برّه والعملات جوه)، بتعد permutations (Combination Sum IV).
static long Combinations(int[] coins, int amount)
{
var ways = new long[amount + 1]; ways[0] = 1;
foreach (var c in coins) // coins outside: each multiset counted once
for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
return ways[amount];
}
static long Permutations(int[] coins, int amount)
{
var ways = new long[amount + 1]; ways[0] = 1;
for (int a = 1; a <= amount; a++) // amount outside: order of coins matters
foreach (var c in coins) if (c <= a) ways[a] += ways[a - c];
return ways[amount];
}
// coins {1,2}, amount 3: Combinations = 2 ({1,1,1},{1,2}), Permutations = 3 (111, 12, 21)ده سؤال follow-up محبوب لأنه بيكشف هل انت فاهم الـ state ولا حافظ الكود.
Kadane كـ DP بمتغير واحد
best_ending_here[i] = أكبر مجموع subarray بتنتهي عند i = max(nums[i], nums[i] + best_ending_here[i−1]): يا تبدأ من جديد عند i، يا تكمل اللي قبلك. الإجابة = أكبر قيمة شفتها. الـ state بتعتمد على اللي قبلها بس ← متغير واحد، O(n) وقت و O(1) مساحة. المثال ده بيوريك إن «الإجابة» مش دايمًا آخر state — هنا هي الـ max على كل الـ states.
public static int MaxSubArray(int[] nums)
{
int endingHere = nums[0], best = nums[0];
for (int i = 1; i < nums.Length; i++)
{
endingHere = Math.Max(nums[i], endingHere + nums[i]);
best = Math.Max(best, endingHere);
}
return best;
}أخطاء شائعة
- State غامضة ← معادلة صح على مثال وغلط على التاني. اكتب التعريف بجملة كاملة.
- Off-by-one بين «أول i عنصر» و«لحد index i». اختار واحد (غالبًا «أول i» مع جدول حجمه n+1) والتزم.
- Loop السعة في الاتجاه الغلط في 0/1 knapsack (تصاعدي = unbounded من غير ما تقصد).
- Memoization بـ key ناقص (نسيت بُعد من الـ state) ← cache بيرجّع إجابة state تانية.
- Recursion عميق ← StackOverflow في .NET (اللي ما ينفعش يتعمله catch). حوّل لـ bottom-up.
- Integer overflow في counting problems: استخدم
longأو modulo زي ما المسألة بتطلب.
اختبر فهمك
في 0/1 knapsack بـ array واحد، ليه loop السعة لازم يبقى تنازلي؟
Greedy (أكبر عملة الأول) بيفشل في Coin Change مع العملات {1, 3, 4} والمبلغ 6. الأمثل؟
Edit distance بين سلسلتين طولهم m و n: التعقيد الزمني والمساحة المحسنة؟
مسائل إنترفيو محلولة
1 (Medium): Longest Increasing Subsequence — من O(n²) لـ O(n log n)
التفكير: dp[i] = طول أطول increasing subsequence بتنتهي عند i. dp[i] = 1 + max(dp[j]) لكل j < i و nums[j] < nums[i] ← O(n²). التحسين: احتفظ بـ tails[k] = أصغر آخر عنصر ممكن لـ subsequence طولها k+1. المصفوفة دي مرتبة دايمًا، فلكل عنصر binary search على أول tail ≥ x واستبدله (أو ضيفه في الآخر) ← O(n log n). طول tails هو الإجابة (مش هو الـ subsequence نفسها).
public static int LengthOfLis(int[] nums)
{
var tails = new List<int>();
foreach (var x in nums)
{
int i = tails.BinarySearch(x);
if (i < 0) i = ~i; // insertion point = first element >= x
if (i == tails.Count) tails.Add(x); else tails[i] = x;
}
return tails.Count;
}2 (Medium): Word Break — هل النص ينفع يتقسم لكلمات من قاموس؟
التفكير: dp[i] = هل أول i حرف ينفع يتقسم. dp[i] = true لو فيه j < i بحيث dp[j] و s[j..i) في القاموس. base: dp[0] = true. HashSet للقاموس، وحد أقصى لطول الكلمة بيقلل الـ j اللي بتجربها. O(n × L).
3 (Medium): Partition Equal Subset Sum
التفكير: لو المجموع الكلي فردي ← false. غير كده السؤال: هل فيه subset مجموعها = sum/2؟ ده 0/1 knapsack بـ boolean: can[w] |= can[w − x] مع loop تنازلي. O(n × sum/2).
4 (Hard): Edit distance مع حد أقصى k — ليه ينفع أسرع؟
التفكير: لو مهتم بس إذا كانت المسافة ≤ k (fuzzy search)، الخلايا اللي بعيدة عن القطر بأكتر من k مستحيل تدّي إجابة ≤ k. احسب «شريط» عرضه 2k+1 حوالين القطر ← O(n × k)، ووقّف بدري لو كل الصف تعدّى k. ده اللي بيخلي fuzzy search على ملايين الأسماء ممكن (مع index زي BK-tree أو n-grams للتصفية الأولية).
أسئلة إنترفيو: Junior → Senior
(Junior) إيه الفرق بين DP و recursion عادي؟
(Junior) إمتى greedy يكفي بدل DP؟
(Mid) حوّل حل memoized لـ bottom-up. إيه اللي لازم تعرفه؟
(Senior) نظام fuzzy search للأسماء العربية بطيء. إزاي تستخدم أفكار الـ DP؟
المراجع والقراءة الإضافية
الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)
مصادر تعليمية ومتقدمة — Third-party & advanced reading
خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.