Software Engineer Encyclopedia
0%
Domain 01 · Computer Science & Programming Fundamentals · Pillar

Dynamic Programming بالعمق: من الـ recursion للـ state design

Dynamic Programming in Depth

إزاي تفكر في الـ DP بدل ما تحفظ حلول: تعريف الـ state، الـ transition، الـ base cases، ترتيب الحساب، وتقليل المساحة — على 1D وGrid وKnapsack وLCS وEdit Distance وIntervals، بمسائل إنترفيو محلولة خطوة بخطوة وتطبيقات حقيقية في .NET والـ AI.

  • Foundation
  • ~13 min read
  • 16 sections
  • 10 code examples
  • 3 diagrams
  • 7 questions
  • Priority L2 · Essential
  • C# 13 / .NET 10 · Python 3.12 (mirrors) · language-independent concepts

بعد الدرس ده هتقدر

  • تتعرف على المسألة اللي ليها حل DP من خلال optimal substructure وoverlapping subproblems
  • تصمم الـ state والـ transition وتكتبهم كمعادلة قبل الكود
  • تحول recursion + memoization لـ tabulation وتقلل المساحة لما ينفع
  • تحل 1D DP وGrid DP و0/1 وunbounded knapsack وLCS وEdit Distance وInterval DP
  • تعيد بناء الحل نفسه (مش القيمة بس) من جدول الـ DP
  • تربط الـ DP بتطبيقات حقيقية: diff، fuzzy matching، WER، Viterbi، وتقسيم الـ budgets

المتطلبات قبل ما تبدأ

01

DP مش مسائل صعبة، DP طريقة تفكير

What dynamic programming really is
Basics

الـ Dynamic Programming = recursion + ذاكرة. لو المسألة الكبيرة بتتحل من مسائل أصغر من نفس النوع (optimal substructure)، والمسائل الأصغر دي بتتكرر كتير (overlapping subproblems)، يبقى بدل ما تحسب نفس الحاجة ألف مرة، تحسبها مرة وتخزنها. كل الصعوبة في خطوة واحدة: تعريف الـ state. بعد كده الكود سهل.

fib(5) naivef(5)f(4)f(3)f(3)f(2)f(2)f(1)f(3) twice, f(2) three times… exponential O(φⁿ)memoized011235each f(i) computed once from f(i-1), f(i-2): O(n)
Naive recursion recomputes the same subproblems; memoization computes each once
الإشارة في المسألةغالبًا DP
«كام طريقة…؟» (counting)نعم — جمع على الاختيارات
«أقل/أكبر تكلفة/طول/ربح» مع اختيارات بتأثر على اللي بعدهانعم — min/max على الاختيارات
«هل ممكن…؟» مع تجربة تركيباتنعم — OR على الاختيارات
Greedy بيبان صح بس عندك مثال مضادنعم غالبًا
محتاج كل الحلول نفسها (مش عددها)لأ — backtracking
02

إطار الـ 5 أسئلة: اكتب المعادلة قبل الكود

The five-question framework
Deep dive
  1. الـ state: إيه أقل معلومات محتاجها عشان أوصف «مسألة فرعية»؟ اكتبها كـ dp[i] أو dp[i][j] بجملة عربي كاملة: «dp[i] = أقل تكلفة للوصول للسلمة i».
  2. الـ transition: لو أنا في الـ state دي، إيه آخر قرار ممكن أكون أخدته؟ الإجابة بتديك المعادلة: dp[i] = cost[i] + min(dp[i−1], dp[i−2]).
  3. الـ base cases: أصغر مسائل إجابتها معروفة من غير حساب.
  4. ترتيب الحساب: كل state لازم تتحسب بعد الـ states اللي بتعتمد عليها (من الصغير للكبير، أو أي topological order).
  5. الإجابة فين؟ 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 + cacheloops بترتيب صريح
بيحسبالـ states اللي محتاجها بسكل الـ states
المخاطرstack overflow مع عمق كبير (10⁵)لازم تعرف ترتيب الحساب
تقليل المساحةصعبسهل (rolling array)

في الإنترفيو: ابدأ بالـ top-down عشان توصل للصح بسرعة، وبعدين حوّل لـ bottom-up لو المحاور سأل عن المساحة أو العمق.

03

1D DP: House Robber و Climbing Stairs و Decode Ways

One-dimensional DP
Practical

House Robber: مسار التفكير

المسألة: بيوت فيها فلوس nums[i]، ما ينفعش تاخد من بيتين جنب بعض. أكبر مجموع؟

  1. Greedy «خد الأكبر» بيفشل: [2, 7, 9, 3, 1] — الأمثل 2+9+1 = 12.
  2. State: dp[i] = أكبر مجموع من البيوت 0..i (مش لازم آخد i).
  3. آخر قرار عند i: يا آخده (فما آخدش i−1): nums[i] + dp[i−2]، يا ما آخدوش: dp[i−1].
  4. dp[i] = max(dp[i−1], nums[i] + dp[i−2])، base: dp[0] = nums[0]، dp[1] = max(nums[0], nums[1]).
  5. كل state بتعتمد على اتنين قبلها بس ← متغيرين بدل array: O(1) مساحة.
C#HouseRobber.cs
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  -> 12

Decode 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 — نفس الإطار، عملية مختلفة.

C#DecodeWays.cs
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;
}
04

Grid DP: Unique Paths و Minimum Path Sum

Two-dimensional grid DP
Practical

dp[r][c] = أقل مجموع للوصول للخلية (r, c) بالتحرك يمين أو تحت بس. آخر خطوة جت من فوق أو من الشمال: dp[r][c] = grid[r][c] + min(dp[r−1][c], dp[r][c−1]). الصف الأول والعمود الأول ليهم طريق واحد بس.

C#MinPathSum.cs: one row of memory
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.

05

Knapsack: 0/1 مقابل unbounded

Knapsack family
Deep dive

0/1: عناصر ليها وزن وقيمة، شنطة سعتها W، كل عنصر مرة واحدة بالكتير. dp[i][w] = أكبر قيمة باستخدام أول i عنصر وسعة w. القرار عند العنصر i: ما آخدوش ← dp[i−1][w]، آخده (لو وزنه ≤ w) ← value[i] + dp[i−1][w − weight[i]].

C#Knapsack01.cs: 1D, iterate capacity DOWNWARDS
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⁹ مش هينفع.

06

String DP: LCS و Edit Distance

Two-sequence DP
Deep dive

مع سلسلتين، الـ 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)

dp[i][j] = min( dp[i-1][j] + 1 (delete), dp[i][j-1] + 1 (insert), dp[i-1][j-1] + (A[i-1] != B[j-1]) )diagupleftcellkitten → sitting = 3k→s (replace), e→i (replace), +g (insert)Used for: fuzzy search ("did you mean"), WER in speech recognition (on words),diff tools (LCS on lines), record de-duplication, OCR post-correction.
Edit distance table for kitten → sitting: each cell takes the cheapest of insert, delete, replace
C#EditDistance.cs: two rows
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.

07

رجّع الحل نفسه مش القيمة بس

Reconstructing the solution
Practical

المحاور كتير بيسأل بعد ما تحسب الرقم: «طب أنهي العناصر؟». الحل: احتفظ بالجدول الكامل (مش النسخة المضغوطة) وامشي بالعكس من الإجابة، وفي كل خلية اسأل «القيمة دي جت منين؟».

C#LCS with reconstruction
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)
08

Interval DP و State design متقدم

Interval DP and richer states
Deep dive

لما المسألة عن «قطعة متصلة [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 cooldowndp[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: اسأل «إيه اللي محتاج أفتكره عن الماضي عشان أقرر الخطوة الجاية صح؟». أي حاجة أقل من كده = إجابات غلط، أي حاجة أكتر = حجم ووقت زيادة.

09

DP في الشغل الحقيقي

Where DP shows up in production
Basics
  • 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).
10

DP كـ state machine: مسائل الأسهم

State-machine DP
Deep dive

مسائل «Best Time to Buy and Sell Stock» بتعلّمك أهم مهارة في الـ DP: لما القرار المسموح بيعتمد على «حالتك»، خلي الحالة جزء من الـ state. مع cooldown (لازم تستنى يوم بعد البيع):

freeno stock, can buyholdown one sharecooldownjust soldbuy: −pricesell: +pricewait one dayrestkeep
Three states per day; each arrow is a transition with its profit effect
C#MaxProfitWithCooldown.cs
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» بتتغير.

11

Combinations مقابل permutations: ترتيب الـ loops بيغير الإجابة

Counting carefully
Deep dive

Coin Change II: عدد الطرق لعمل مبلغ بعملات غير محدودة. لو الـ loop الخارجي على العملات والداخلي على المبلغ، بتعد combinations (1+2 و2+1 نفس الطريقة). لو العكس (المبلغ برّه والعملات جوه)، بتعد permutations (Combination Sum IV).

C#two orders, two different answers
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 ولا حافظ الكود.

12

Kadane كـ DP بمتغير واحد

Maximum subarray as DP
Practical

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.

C#Kadane.cs
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;
}
13

أخطاء شائعة

Common mistakes
Basics
  • 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 زي ما المسألة بتطلب.
14

اختبر فهمك

Knowledge check
Basics

في 0/1 knapsack بـ array واحد، ليه loop السعة لازم يبقى تنازلي؟

Greedy (أكبر عملة الأول) بيفشل في Coin Change مع العملات {1, 3, 4} والمبلغ 6. الأمثل؟

Edit distance بين سلسلتين طولهم m و n: التعقيد الزمني والمساحة المحسنة؟

15

مسائل إنترفيو محلولة

Interview problems, solved with reasoning
Practical
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 نفسها).

C#LIS.cs
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 للتصفية الأولية).

16

أسئلة إنترفيو: Junior → Senior

Interview ladder
Basics
(Junior) إيه الفرق بين DP و recursion عادي؟
الـ DP recursion على مسائل فرعية متكررة مع تخزين نتايجها، فكل مسألة فرعية بتتحسب مرة واحدة؛ ده بيحول التعقيد غالبًا من exponential لـ polynomial.
(Junior) إمتى greedy يكفي بدل DP؟
لما تقدر تثبت إن الاختيار المحلي الأفضل دايمًا جزء من حل أمثل (greedy choice property)، زي interval scheduling بأقل وقت انتهاء. لو لقيت مثال مضاد واحد، استخدم DP.
(Mid) حوّل حل memoized لـ bottom-up. إيه اللي لازم تعرفه؟
ترتيب الاعتمادية بين الـ states (مين محتاج مين)، عشان تعمل loops تحسب كل state بعد اعتمادياتها، والـ base cases كقيم ابتدائية في الجدول.
(Senior) نظام fuzzy search للأسماء العربية بطيء. إزاي تستخدم أفكار الـ DP؟
normalization عربي الأول (الألف، الياء، التاء المربوطة)، تصفية مرشحين بـ n-gram index أو trigram في PostgreSQL، وبعدين edit distance محدود بـ k على المرشحين بس مع early exit، و cache للاستعلامات المتكررة. والقياس على dataset أسماء حقيقي بـ recall/latency.
↗

المراجع والقراءة الإضافية

References & further reading

الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)

خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.

محتويات الدرس