Dynamic Programming 22D states · grid dp · two strings · 0/1 knapsack

في الفصل اللي فات كل state كانت رقم واحد dp[i]. هنا الإجابة بتعتمد على حاجتين مع بعض، فالـ dp بقى جدول dp[i][j]. نفس الـ recipe بالظبط، بس في بعدين، ومعاها سؤال جديد: كل خانة بتبص على أنهي خانات؟

قبله: Dynamic Programming 1 بيمهّد لـ: Greedy

هتطلع من الفصل ده وإنت عارف

  • تعرف إمتى الـ state محتاج رقمين، وتبني الـ table وتعرف كل خانة بتعتمد على مين (فوق، شمال، قطري).
  • تحل مسائل الـ grid: Unique Paths و Unique Paths II و Minimum Path Sum.
  • تحل مسائل الـ two strings: LCS (وتطلّع الـ subsequence نفسها بالرجوع في الجدول) و Edit Distance بعملياتها التلاتة.
  • تفهم الـ 0/1 knapsack، وتحل Partition Equal Subset Sum بـ 1D array، وتعرف ليه الـ loop بترجع لورا.
  • تفرّق بين عدّ combinations وعدّ permutations في Coin Change II، بترتيب الـ loops بس.
  • تتعرّف على أي مسألة DP من شكلها، ومعاك جدول بالـ states المشهورة.

ليه 2D؟ لما الـ state محتاج رقمين

في DP 1 كان i لوحده كفاية يوصف المكان: الدرجة رقم كام، أول كام بيت. بس خد المسألة دي: robot واقف في أول خانة من grid، وبيتحرك يمين أو تحت بس. بكام طريقة يوصل للركن التحتاني اليمين؟

عشان توصف مكانه محتاج رقمين: الصف والعمود. ومحتاج رقمين = الـ dp بقى جدول. خلّينا نشوف الـ recursion الساذجة الأول، وكل خانة مكتوب فيها عدد مرات ما اتحسبت:

19 call على 12 خانة، وخانات اتحسبت 3 مرات. نفس الـ overlapping subproblems بتاعة fib، بس على جدول. والحل نفسه: نحسب كل خانة مرة واحدة ونكتبها في dp[r][c].

تشبيه إنت في شوارع وسط البلد، والشوارع grid، ومسموحلك تمشي شرق أو جنوب بس. عدد الطرق لأي تقاطع = الطرق اللي جاية من التقاطع اللي شماله + اللي جاية من التقاطع اللي فوقه. لو كتبت الرقم على كل تقاطع وإنت ماشي، أي تقاطع جديد بتحسبه بجمع رقمين مكتوبين قبل كده.

قراية الجدول: كل خانة بتبص على مين؟

طب إزاي تعرف من كلام المسألة إن الـ state هيبقى رقمين؟

إزاي تعرفه من المسألة

اسأل: "الـ recursion الساذجة بتاعتي بتاخد كام parameter بيتغيّر؟". لو اتنين، يبقى جدول. وفيه 3 عائلات بتتكرر كتير:

لما تشوف: grid + move right / downtwo stringscommon subsequenceconvert word1 to word2 items + capacity / budgetpartition into two equal sumsnumber of combinations to make amount
ومش هو غالبًا لو: grid + move in 4 directions + shortest path (BFS)grid + count islands (DFS)

خلي بالك من آخر سطر: لو الـ grid فيه حركة في 4 اتجاهات، ممكن ترجع لخانة كنت فيها، فمفيش ترتيب ثابت للخانات، ودي graph مش DP. الـ DP على grid بيشتغل لما الحركة في اتجاه واحد (يمين وتحت) فالجدول بيتملي بترتيب.

العيلةالـ stateبتبص علىمسائل
Griddp[r][c] = الإجابة لحد الخانة ديفوق وشمال62، 63، 64
Two stringsdp[i][j] = الإجابة لأول i حروف من الأولى وأول j من التانيةفوق، شمال، قطري1143، 72، 583
Knapsackdp[i][s] = أول i items بـ capacity أو مجموع sالصف اللي فوق: نفس العمود، وعمود أصغر416، 494، 518
flowchart TD
  A["DP problem"] --> B{"How many changing parameters in the recursion?"}
  B -- "one" --> C["1D dp (previous chapter)"]
  B -- "two" --> D{"What are they?"}
  D -- "row, col" --> G["Grid dp: look up and left"]
  D -- "prefix of s1, prefix of s2" --> S["Two-string dp: up, left, diagonal"]
  D -- "item index, capacity" --> K["Knapsack: row above; often squeezed to 1D"]
  

يلا نبدأ بأبسطهم: grid، والـ robot اللي فوق.

مثال محلول 1: Unique Paths

Unique Paths

mediumLeetCode 62

grid فيه m صف و n عمود. robot في (0, 0) وبيتحرك يمين أو تحت بس. كام طريق مختلف يوصّله لـ (m - 1, n - 1)؟

Input: m = 3, n = 4 → 10 Input: m = 3, n = 2 → 3 Input: m = 1, n = 1 → 1

الجديد هنا إن الـ table بقى 2D، وكل خانة بتبص على فوق وشمال.

نفكّر فيها مع بعض (بالـ recipe)

  1. الـ state: dp[r][c] = عدد الطرق من (0, 0) لحد (r, c).
  2. الـ transition (آخر حركة): وصلت لـ (r, c) يا من فوق (r - 1) يا من الشمال (c - 1)، والنوعين مختلفين: dp[r][c] = dp[r - 1][c] + dp[r][c - 1].
  3. الـ base cases: أول صف كله 1 (يمين على طول) وأول عمود كله 1 (تحت على طول).
  4. الترتيب: صف صف، من الشمال لليمين. الإجابة: dp[m - 1][n - 1]. الحجم: m × n، لأن الـ states هي الخانات نفسها.
  1. ليه Array.from؟ new Array(m).fill(new Array(n).fill(0)) بتحط نفس الصف في كل الخانات (reference واحد)، فأي تعديل في صف بيظهر في كلهم. جرّبتها: bad[0][0] = 5 خلّت أول عمود كله 5.
  2. < m و < n، لأن الـ states هنا indices الخانات (من 0 لـ m - 1).
  3. الـ base cases جوه نفس الـ loop. الـ || عشان أي خانة في أول صف أو أول عمود.
  4. الخانتين جاهزين لأننا بنلف صف صف من الشمال.
  5. الركن التحتاني: m - 1 و n - 1 مش m و n.

الخانة الصفرا بتتملي، والتركوازي هما فوق وشمال اللي بنجمعهم:

التعقيد: O(m · n) وقت و memory. ولأن كل صف محتاج اللي فوقه بس، تقدر تخلّيها صف واحد O(n): row[c] += row[c - 1]. (وفيه حل رياضي C(m + n - 2, m - 1)، بس الـ interviewer عايز يشوف الـ DP.)

هنا كل الخانات مفتوحة. طب لو فيه صخور في الطريق؟

مثال محلول 2: Unique Paths II (فيه صخور)

Unique Paths II

mediumLeetCode 63

نفس المسألة، بس الـ grid فيه 1 = صخرة مينفعش تعدّي منها، و 0 = فاضية.

Input: grid = [[0, 0, 1, 0], [0, 0, 0, 0], [0, 1, 0, 0]] Output: 4 Input: grid = [[1]] → 0

الجديد هنا إن الـ base cases مش "1 على طول": أول صف بعد صخرة كله 0.

  1. الصخرة: dp = 0، محدش يعدّي منها، فهي مش بتساهم في اللي بعدها.
  2. الفخ: في المسألة اللي فاتت ملّينا أول صف بـ 1. هنا لو فيه صخرة في أول صف، كل اللي بعدها في الصف ده 0، لأن مفيش طريق ليهم غير من الشمال، والشمال مقفول. جرّبتها: لو ملّيت أول صف وأول عمود 1 زي الأول، الإجابة تطلع 7 بدل 4.
  3. الحل الأنضف: بدل حالات خاصة للصف والعمود، كل خانة = فوق (لو موجود) + شمال (لو موجود)، والبداية 1.
  1. الصخرة الأول، قبل البداية: لو (0, 0) نفسها صخرة، الإجابة 0 ([[1]] → 0).
  2. البداية: طريق واحد (إنك واقف).
  3. بدل if خاص للصف الأول: لو مفيش فوق، المساهمة 0. ده بيعالج الصخرة في أول صف لوحده من غير ما تفكّر فيها.

الخانات الرمادي صخور:

التعقيد: O(m · n).

لحد دلوقتي بنعدّ طرق. طب لو كل خانة ليها تكلفة، وعايز أرخص طريق؟

مثال محلول 3: Minimum Path Sum

Minimum Path Sum

mediumLeetCode 64

grid أرقام موجبة. امشي من (0, 0) لـ (m - 1, n - 1) يمين أو تحت بس. إيه أقل مجموع للخانات اللي عدّيت عليها (شاملة البداية والنهاية)؟

Input: grid = [[1, 4, 1, 2], [2, 7, 1, 3], [6, 1, 1, 1]] Output: 9 (1 → 4 → 1 → 1 → 1 → 1)

الجديد هنا إن الـ transition = min + تكلفة الخانة، فأول صف وأول عمود بقوا مجموع تراكمي مش 1.

  1. الـ state: dp[r][c] = أقل مجموع من (0, 0) لحد (r, c) شاملة الخانة.
  2. الـ transition: min(فوق، شمال) + grid[r][c].
  3. الـ base: dp[0][0] = grid[0][0]. أول صف: من الشمال بس. أول عمود: من فوق بس.
  4. ليه مش greedy؟ "روح للجار الأصغر" من (0, 0) هيختار 2 (تحت) بدل 4، ويوصل لـ 12 (1، 2، 6، 1، 1، 1). الـ DP بيشوف إن الـ 4 بتفتح طريق أرخص بعدها.
  1. جدول منفصل عشان ما نعدّلش الـ input. ممكن تكتب في grid نفسه وتوفّر الـ memory، بس قول للـ interviewer إنك بتعدّل الـ input.
  2. مش ممكن تاخد min مع خانة مش موجودة: dp[-1] = undefined، و Math.min(undefined, 5) = NaN.
  3. الأرخص من الاتنين + تمن الخانة نفسها.

فوق الجدول: الـ dp. تحته: الـ grid الأصلي، والخانة الصفرا هي اللي بنضيف تمنها:

التعقيد: O(m · n) وقت، و O(m · n) أو O(n) بصف واحد أو O(1) لو كتبت في الـ grid.

في الـ grid، الرقمين كانوا صف وعمود. طب لو الرقمين مكان في string ومكان في string تاني؟

مثال محلول 4: Longest Common Subsequence

Longest Common Subsequence

mediumLeetCode 1143

عندك اتنين strings. إيه طول أطول subsequence موجودة في الاتنين؟ (subsequence = حروف بنفس الترتيب، مش لازم جنب بعض.)

Input: text1 = "cake", text2 = "brake" Output: 3 ("ake") Input: text1 = "abc", text2 = "def" Output: 0

الجديد هنا تلات حاجات: الـ axes بقوا strings، والجدول (m + 1) × (n + 1) بصف وعمود للـ empty prefix، وظهر الـ قطري.

نفكّر فيها مع بعض (بالـ recipe)

  1. Brute force: كل subsequence من الأولى (2ᵐ) وتشوفها في التانية. مستحيل مع m = 1000.
  2. الـ state: dp[i][j] = طول الـ LCS بين أول i حروف من text1 وأول j حروف من text2.
  3. الـ transition (آخر حرفين): بص على text1[i - 1] و text2[j - 1].
    لو زي بعض: الحرف ده جزء من الـ LCS، والباقي من غيرهم: dp[i - 1][j - 1] + 1 (القطري).
    لو مختلفين: واحد فيهم مش في الـ LCS. يا نشيل حرف من الأولى (dp[i - 1][j]، فوق)، يا من التانية (dp[i][j - 1]، شمال)، وناخد الأكبر.
  4. الـ base: dp[0][j] = dp[i][0] = 0: string فاضي مالوش حاجة مشتركة. عشان كده الحجم m + 1 و n + 1: الصف 0 والعمود 0 للـ empty prefix.
  5. الترتيب: i من 1 لـ m و j من 1 لـ n (شاملين). الإجابة: dp[m][n].
  1. m + 1 صف و n + 1 عمود. الصف 0 والعمود 0 بيفضلوا 0 من الـ fill، ودول الـ base cases.
  2. من 1 لـ m شاملة (<=)، لأن dp[m][n] هي الإجابة.
  3. الـ off-by-one بتاع الفصل: dp[i][j] بتتكلم عن أول i حروف، وآخرهم text1[i - 1]. لو كتبت text1[i]، هتقارن الحرف اللي بعده، وفي آخر لفة undefined.
  4. القطري: الاتنين اتشالوا مع بعض لأنهم اتطابقوا.
  5. مش + 1 هنا: مفيش حرف اتضاف للـ LCS.

الـ text1 على الصفوف و text2 على الأعمدة، والـ "" هو الـ empty prefix. الحرفين اللي بنقارنهم بيتلوّنوا:

نطلّع الـ subsequence نفسها: نرجع في الجدول

الجدول بيدّي الطول بس. عشان تطلّع الحروف، ابدأ من dp[m][n] وارجع ورا القرار اللي عمل كل خانة: لو الحرفين زي بعض، الحرف ده في الـ LCS ونروح قطري، وإلا نروح ناحية الخانة الأكبر (فوق أو شمال).

  1. بنقف أول ما نوصل للصف 0 أو العمود 0: مفيش حروف تانية.
  2. زي بعض = الخانة دي اتعملت من القطري + 1. ناخد الحرف ونروح قطري.
  3. مختلفين = الخانة اتعملت من الأكبر في فوق وشمال، فنمشي ناحيته. لو متساويين، أي واحد صح (وممكن يطلّع LCS مختلفة بنفس الطول).
  4. جمعنا الحروف من الآخر للأول، فنعكس.

التعقيد: O(m · n) وقت و memory. الرجوع O(m + n).

في LCS كان عندنا choice: نشيل حرف من هنا أو من هنا. طب لو عندنا 3 عمليات، ولكل واحدة تمن؟

مثال محلول 5: Edit Distance

Edit Distance

mediumLeetCode 72

حوّل word1 لـ word2 بأقل عدد عمليات. العمليات: insert حرف، delete حرف، replace حرف بحرف.

Input: word1 = "rain", word2 = "shine" Output: 3 (replace r → s, replace a → h, insert e) Input: word1 = "", word2 = "abc" Output: 3 (three inserts)

الجديد هنا إن كل عملية من التلاتة = خانة جارة (قطري، فوق، شمال)، وإن الـ base row/col بقوا i و j مش 0.

نفكّر فيها مع بعض (بالـ recipe)

  1. الـ state: dp[i][j] = أقل عمليات تحوّل أول i حروف من word1 لأول j حروف من word2.
  2. الـ transition (آخر عملية على آخر حرف):
    الحرفين زي بعض: مش محتاجين حاجة: dp[i - 1][j - 1].
    Replace word1[i - 1] بـ word2[j - 1]: الاتنين اتظبطوا، فاضل dp[i - 1][j - 1] (قطري) + 1.
    Delete word1[i - 1]: فاضل نحوّل أول i - 1 لأول j: dp[i - 1][j] (فوق) + 1.
    Insert word2[j - 1] في الآخر: الحرف ده اتظبط، فاضل أول i لأول j - 1: dp[i][j - 1] (شمال) + 1.
  3. الـ base: dp[i][0] = i (تمسح i حروف عشان توصل لـ ""). dp[0][j] = j (تعمل j inserts من ""). مش 0، لأن التحويل من أو لـ string فاضي ليه تمن.
  4. الترتيب: صف صف. الإجابة: dp[m][n]. الحجم: (m + 1) × (n + 1).
  1. الـ base row والـ column. لو سبتهم 0 من الـ fill، "" → "abc" هتطلع 0.
  2. زي بعض = ببلاش. مش min(...) هنا، ولا + 1.
  3. التلات جيران، كل واحد عملية. الـ 1 + برا الـ min لأن أي عملية فيهم بتتكلف 1.

word1 = "rain" على الصفوف و word2 = "shine" على الأعمدة:

الجارالعمليةمعناها
القطري dp[i-1][j-1]replace (أو ببلاش لو زي بعض)آخر حرف في الاتنين اتظبط
فوق dp[i-1][j]deleteشلنا آخر حرف من word1
شمال dp[i][j-1]insertضفنا آخر حرف بتاع word2

التعقيد: O(m · n) وقت و memory، أو O(n) بصفين.

في الانترفيو Edit Distance من أشهر مسائل الـ DP. الـ interviewer عايز يسمع منك إن كل عملية = خانة جارة، وليه الـ base row هو j. ارسم جدول 3 × 3 صغير على الورقة قبل الكود.

في الـ two strings الرقمين كانوا prefixes. فيه نوع تالت مهم جدًا: items وسعة.

مثال محلول 6: 0/1 Knapsack و Partition Equal Subset Sum

الـ 0/1 knapsack الأصلية: عندك items، كل واحد ليه وزن وقيمة، وشنطة بتشيل وزن معيّن. تختار items (كل واحد مرة واحدة: 0 أو 1، ومن هنا الاسم) عشان أكبر قيمة. الـ state: dp[i][w] = أحسن قيمة من أول i items بـ capacity w. ولكل item قرارين: سيبه (dp[i - 1][w]) أو خده (dp[i - 1][w - weight] + value).

Partition Equal Subset Sum

mediumLeetCode 416

هل تقدر تقسم الـ array لجزئين مجموعهم متساوي؟

Input: nums = [1, 2, 3] → true ({1, 2} and {3}) Input: nums = [1, 2, 5] → false Input: nums = [2] → false

الجديد هنا إن الـ state فيه capacity (مجموع)، وكل item مرة واحدة. وهنشوف إزاي الجدول بيتقلص لـ 1D، وليه الـ loop لازم ترجع لورا.

نفكّر فيها مع بعض (بالـ recipe)

  1. إعادة صياغة: لو المجموع الكلي total فردي، مستحيل. لو زوجي، السؤال بقى: "فيه subset مجموعها total / 2؟". ده knapsack: الشنطة = target، وعايزين نملاها بالظبط.
  2. الـ state: dp[i][s] = هل فيه subset من أول i أرقام مجموعها s بالظبط؟
  3. الـ transition: الرقم x = nums[i - 1] يا سبناه: dp[i - 1][s]، يا أخدناه: dp[i - 1][s - x]. الاتنين من الصف اللي فوق، لأن كل رقم مرة واحدة.
  4. الـ base: dp[0][0] = true (صفر أرقام = مجموع 0)، والباقي false.
  5. الإجابة: dp[n][target]. الحجم: (n + 1) × (target + 1).
  1. Early return: فردي يبقى مستحيل، ومش محتاجين أي جدول.
  2. target + 1 عمود: المجاميع من 0 لـ target شاملة.
  3. Skip: نفس إجابة الصف اللي فوق.
  4. Take: من الصف اللي فوق (i - 1)، يعني من غير x. ده اللي بيضمن إن x اتاخد مرة واحدة. و s >= x عشان ما نقراش index سالب.

الصفوف = عدد الأرقام اللي اتاحت (i)، والأعمدة = المجموع (s). T = ممكن، F = لأ:

من 2D لـ 1D: وليه الـ loop بترجع لورا

كل صف بيقرا من الصف اللي فوقه بس. فنقدر نستخدم صف واحد ونكتب فوقه. المشكلة: لما نكتب dp[s] الجديدة، الخانات لسه فيها قيم الصف القديم، ولازم dp[s - x] اللي بنقراها تبقى قديمة (من غير x). لو لفّينا من الكبير للصغير، s - x أصغر من s، يعني لسه ما اتكتبش في اللفة دي، فهو قديم. ده الـ key insight.

  1. صف واحد بدل الجدول: O(target) memory.
  2. لورا، و s >= x عشان s - x ما يبقاش سالب. والخانات الأصغر من x مش بتتلمس، وده صح: مش ممكن تتأثر بـ x.
  3. "skip" مش مكتوبة: لو ما اتغيّرتش، dp[s] فاضلة بقيمتها القديمة، وده هو الـ skip.

دلوقتي شوف إيه اللي بيحصل لو الـ loop راحت لقدّام، على [1, 2, 5] (الإجابة الصح false: مفيش subset مجموعها 4):

لقدّام، dp[s - x] ممكن تكون لسه اتعملت بنفس الـ x في نفس اللفة، فالـ x بيتاخد مرتين وتلاتة. ده بالظبط "unbounded knapsack" (تكرار مسموح)، وهتشوفه صح في المثال الجاي.

التعقيد: O(n · target) وقت، و O(target) memory بالـ 1D.

هنا كل رقم مرة واحدة، فالـ loop لورا. طب لو التكرار مسموح، وعايزين نعدّ الطرق؟

مثال محلول 7: Coin Change II

Coin Change II

mediumLeetCode 518

عملات coins بعدد مالوش آخر. كام طريقة تعمل بيها المبلغ amount؟ 1 + 2 و 2 + 1 طريقة واحدة (combinations).

Input: amount = 4, coins = [1, 2, 3] Output: 4 (1+1+1+1, 1+1+2, 2+2, 1+3) Input: amount = 3, coins = [2] Output: 0

الجديد هنا إن ترتيب الـ loops بيغيّر الإجابة: coins برا = combinations، amounts برا = permutations. وكمان الـ loop لقدّام بقت صح لأن التكرار مسموح.

نفكّر فيها مع بعض (بالـ recipe)

  1. الـ state: dp[a] = عدد الطرق تعمل a بالعملات اللي اتعاملنا معاها لحد دلوقتي.
  2. الـ transition: لما نضيف عملة c: الطرق اللي فيها c على الأقل مرة = dp[a - c]. فـ dp[a] += dp[a - c].
  3. الـ base: dp[0] = 1: طريقة واحدة تعمل 0، ما تاخدش حاجة. (زي dp[0] = 1 في Climbing Stairs.)
  4. ليه الـ coins برا؟ كده بنضيف العملات نوع نوع: الأول كل الطرق بالـ 1 بس، وبعدين نسمح بالـ 2، وهكذا. فأي combination بتتعدّ مرة واحدة بترتيب ثابت (الـ 1 قبل الـ 2 دايمًا)، و 2 + 1 عمرها ما تتعدّ لوحدها. نفس فكرة الـ start index في الـ backtracking.
  5. ليه لقدّام؟ عشان dp[a - c] تبقى شاملة طرق فيها c نفسها، يعني c يتكرر. ده عكس الـ 0/1 knapsack بالظبط.
  1. عدّ = init بـ 0.
  2. من غيره كل حاجة تفضل 0، لأن كل طريقة في الآخر بتبدأ من 0.
  3. العملات برا: ده اللي بيخلّينا نعدّ combinations.
  4. من c عشان a - c >= 0، و لقدّام عشان التكرار مسموح.
  5. += مش =: بنضيف الطرق الجديدة اللي فيها c على الطرق القديمة اللي من غيرها.

نفس الكود بترتيب loops معكوس

هنا لكل مبلغ بنجرّب كل عملة كـ آخر عملة، فـ 1 + 2 (آخرها 2) و 2 + 1 (آخرها 1) بيتعدّوا طريقتين. ده عدد permutations، وهو بالظبط حل Combination Sum IV (377).

الـ loop البرّانيةالـ loop الجوّانيةبتعدّمسألة
coinsamounts لقدّامcombinations، والعملة تتكرر518
amountscoinspermutations (الترتيب فارق)377
itemscapacity لوراكل item مرة واحدة (0/1)416، 494

التعقيد: O(amount × coins.length) وقت، و O(amount) memory.

شفنا 3 عائلات 2D. يلا نجمع كل الـ DP اللي شفناه في الفصلين في خريطة واحدة.

إزاي تعرف إنها DP، وأشهر الـ states

تلات أنواع أسئلة، وفيهم choices في كل خطوة، والـ subproblems بتتكرر:

ولو المسألة عايزة كل الإجابات نفسها، يبقى backtracking. ولو فيه choice بتقدر تثبت إنه الأحسن دايمًا، يبقى greedy أبسط.

العيلةالـ stateالـ transitionأمثلة
1D prefixdp[i] = answer for the first iمن i - 1 و i - 270، 198، 91
1D ending at idp[i] = best ending exactly at iمن كل j < i، والإجابة max300، 53
1D amountdp[a] = best / ways for amount aloop على الـ coins322، 279، 377
1D split pointdp[i] = can the prefix i be splitloop على مكان القطع j139
Griddp[r][c] = answer up to cell (r, c)فوق وشمال62، 63، 64، 221
Two stringsdp[i][j] = prefixes i and jقطري لو زي بعض، وإلا فوق / شمال1143، 72، 583
0/1 knapsackdp[i][s] → dp[s], s backwardsskip / take من الصف اللي فوق416، 494
Unbounded knapsackdp[s], s forwardsskip / take من نفس الصف518، 322
Intervaldp[l][r] = answer for s[l..r]من intervals أصغر جواه516، 5
State machinedp[i][holding] = best on day ibuy / sell / rest309، 122
لما تتزنق في state اكتب الـ backtracking الساذج الأول، وبص على الـ parameters اللي بتتغيّر في الـ recursion. هما دول الـ state. لو parameter واحد: dp[i]. لو اتنين: جدول. وبعدين حط memo، وبعدين حوّلها table.

قبل ما تحل لوحدك، دي الغلطات اللي بتتكرر في الـ 2D.

غلطات مشهورة

1. الصفوف كلها نفس الـ array

نفس مشكلة res.push(path) في الـ backtracking: reference واحد. Array.from بتنادي الدالة لكل صف.

2. نسيت الصف والعمود الزيادة في الـ strings

القاعدة: dp[i][j] = "أول i و أول j"، والجدول (m + 1) × (n + 1)، والحرف [i - 1]، والإجابة dp[m][n]. الأربعة مع بعض.

3. ملّيت أول صف 1 على طول وفيه صخرة

4. الـ 0/1 knapsack بـ loop لقدّام

مرة واحدة = لورا. تكرار مسموح = لقدّام.

5. ترتيب الـ loops في عدّ الطرق

coins برا = combinations (518). amounts برا = permutations (377). اقرا المسألة: هل 1 + 2 و 2 + 1 طريقة واحدة؟

6. الـ base row في Edit Distance

يلا نختبر الكلام ده.

اختبر نفسك

في LCS، لو text1[i - 1] === text2[j - 1]، dp[i][j] = ؟

  • max(dp[i - 1][j], dp[i][j - 1])
  • dp[i - 1][j - 1] + 1
  • dp[i - 1][j] + 1
  • dp[i][j - 1] + 1

الحرفين اتطابقوا، فبيتشالوا مع بعض (القطري) والطول يزيد 1. فوق + 1 ممكن تعدّ نفس الحرف مرتين.

في Partition بـ 1D، ليه s بتلف من target لتحت؟

  • عشان نوصل للإجابة أسرع
  • عشان dp[s - x] اللي بنقراها تبقى لسه من غير x، فالرقم يتاخد مرة واحدة
  • عشان نتجنب index سالب
  • مش فارقة

s - x < s، فلو بنلف لورا، الخانة الأصغر لسه ما اتكتبتش في اللفة دي. لقدّام هتكون اتكتبت بنفس x، فيتاخد مرتين.

Coin Change II بالـ amounts برا والـ coins جوه، على [1, 2, 3] و 4، هترجّع كام؟

  • 4
  • 7
  • 3
  • 8

بتعدّ permutations: 1111، و 112 بـ 3 ترتيبات، و 22، و 13 بترتيبين = 1 + 3 + 1 + 2 = 7.

في Edit Distance، ليه dp[0][j] = j؟

  • عشان كده الـ convention
  • عشان من string فاضي لأول j حروف لازم j inserts
  • عشان j deletes
  • عشان الـ index بيبدأ من 1

الـ base case = تمن حقيقي. dp[i][0] = i deletes، و dp[0][j] = j inserts.

const g = new Array(3).fill(new Array(3).fill(0)); g[1][2] = 7; كام خانة قيمتها 7؟

  • 1
  • 3
  • 9
  • 0، هيضرب error

التلات صفوف هما نفس الـ array، فـ g[0][2] و g[1][2] و g[2][2] كلهم 7.

تمرين: فكّر قبل ما تفتح

Longest Palindromic Subsequence

mediumLeetCode 516

إيه طول أطول subsequence في s بتتقري زي ما هي من الناحيتين؟

"character" → 5 ("carac") "racecar" → 7 "a" → 1
تلميح 1

الـ palindrome بيتقري نفس الحاجة لو عكسته. يعني الـ subsequence دي موجودة في s وفي s معكوسة.

تلميح 2

دي LCS بين s و reverse(s). ممكن تعيد استخدام الكود اللي فوق زي ما هو.

الحل

جرّبتها: "character" → 5، "racecar" → 7، "a" → 1. فيه حل تاني بـ interval DP (dp[l][r] على s[l..r]) بنفس الـ O(n²)، بس فكرة الـ LCS أسرع تكتبها في الانترفيو.

لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

قبل الكود، ارسم جدول صغير (3 × 4 كفاية) واملا أول كام خانة بإيدك، وعلّم كل خانة بتبص على مين.

وفي الآخر، الفصل كله في صفحة واحدة.

الخلاصة

في جملة واحدة لما الـ recursion بتاعتك فيها رقمين بيتغيّروا، الـ dp بقى جدول: اعرف كل خانة بتبص على أنهي جيران، ولِف بترتيب يخلّيهم جاهزين، وخلي بالك من الصف والعمود الزيادة.
السؤالالإجابة
الجدول m × n ولا (m + 1) × (n + 1)؟Grid: الخانات نفسها، m × n. Strings / knapsack: محتاج حالة فاضية، فـ + 1.
كل خانة بتبص على مين؟Grid: فوق وشمال. Strings: قطري لو زي بعض، وإلا فوق وشمال (وفي Edit Distance التلاتة).
الـ base row / col؟Unique Paths: 1 (بس الصخور 0). LCS: 0. Edit Distance: i و j. Min Path Sum: مجموع تراكمي.
1D: لورا ولا لقدّام؟كل item مرة واحدة: لورا. تكرار مسموح: لقدّام.
عدّ: أنهي loop برا؟combinations: الـ items برا. permutations: الـ amount برا.
عايز الحل نفسه مش الرقم بس؟املا الجدول، وارجع فيه من الآخر ورا القرار اللي عمل كل خانة.

الفصل الجاي: الـ DP بيجرّب كل الـ choices عشان مش واثق مين الأحسن. بس ساعات فيه choice تقدر تثبت إنه الأحسن دايمًا، زي الفكة المصرية أو "خد الاجتماع اللي بيخلص الأول". ساعتها مش محتاج جدول خالص، قرار واحد في كل خطوة. ده الـ Greedy، والسؤال المهم فيه هيبقى: إمتى الـ greedy صح، وإمتى بيقع زي ما وقع في Coin Change؟