Dynamic Programming 22D states · grid dp · two strings · 0/1 knapsack
في الفصل اللي فات كل state كانت رقم واحد dp[i]. هنا الإجابة بتعتمد على حاجتين مع بعض، فالـ dp بقى جدول dp[i][j]. نفس الـ recipe بالظبط، بس في بعدين، ومعاها سؤال جديد: كل خانة بتبص على أنهي خانات؟
هتطلع من الفصل ده وإنت عارف
- تعرف إمتى الـ 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].
قراية الجدول: كل خانة بتبص على مين؟
- الـ dependencies: في الـ grid غالبًا فوق
dp[r - 1][c]و شمالdp[r][c - 1]. في الـ two strings بيزيد القطريdp[i - 1][j - 1]. - ترتيب اللفّ: صف صف من فوق لتحت، وجوه كل صف من الشمال لليمين. كده فوق وشمال والقطري دايمًا جاهزين قبل الخانة.
- الـ base cases: أول صف وأول عمود، لأن مفيش فوق أو مفيش شمال.
طب إزاي تعرف من كلام المسألة إن الـ state هيبقى رقمين؟
إزاي تعرفه من المسألة
اسأل: "الـ recursion الساذجة بتاعتي بتاخد كام parameter بيتغيّر؟". لو اتنين، يبقى جدول. وفيه 3 عائلات بتتكرر كتير:
خلي بالك من آخر سطر: لو الـ grid فيه حركة في 4 اتجاهات، ممكن ترجع لخانة كنت فيها، فمفيش ترتيب ثابت للخانات، ودي graph مش DP. الـ DP على grid بيشتغل لما الحركة في اتجاه واحد (يمين وتحت) فالجدول بيتملي بترتيب.
| العيلة | الـ state | بتبص على | مسائل |
|---|---|---|---|
| Grid | dp[r][c] = الإجابة لحد الخانة دي | فوق وشمال | 62، 63، 64 |
| Two strings | dp[i][j] = الإجابة لأول i حروف من الأولى وأول j من التانية | فوق، شمال، قطري | 1143، 72، 583 |
| Knapsack | dp[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
grid فيه m صف و n عمود. robot في (0, 0) وبيتحرك يمين أو تحت بس. كام طريق مختلف يوصّله لـ (m - 1, n - 1)؟
الجديد هنا إن الـ table بقى 2D، وكل خانة بتبص على فوق وشمال.
نفكّر فيها مع بعض (بالـ recipe)
- الـ state:
dp[r][c]= عدد الطرق من(0, 0)لحد(r, c). - الـ transition (آخر حركة): وصلت لـ
(r, c)يا من فوق (r - 1) يا من الشمال (c - 1)، والنوعين مختلفين:dp[r][c] = dp[r - 1][c] + dp[r][c - 1]. - الـ base cases: أول صف كله 1 (يمين على طول) وأول عمود كله 1 (تحت على طول).
- الترتيب: صف صف، من الشمال لليمين. الإجابة:
dp[m - 1][n - 1]. الحجم:m × n، لأن الـ states هي الخانات نفسها.
- ليه
Array.from؟new Array(m).fill(new Array(n).fill(0))بتحط نفس الصف في كل الخانات (reference واحد)، فأي تعديل في صف بيظهر في كلهم. جرّبتها:bad[0][0] = 5خلّت أول عمود كله 5. < mو< n، لأن الـ states هنا indices الخانات (من 0 لـm - 1).- الـ base cases جوه نفس الـ loop. الـ
||عشان أي خانة في أول صف أو أول عمود. - الخانتين جاهزين لأننا بنلف صف صف من الشمال.
- الركن التحتاني:
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 (فيه صخور)
نفس المسألة، بس الـ grid فيه 1 = صخرة مينفعش تعدّي منها، و 0 = فاضية.
الجديد هنا إن الـ base cases مش "1 على طول": أول صف بعد صخرة كله 0.
- الصخرة:
dp = 0، محدش يعدّي منها، فهي مش بتساهم في اللي بعدها. - الفخ: في المسألة اللي فاتت ملّينا أول صف بـ 1. هنا لو فيه صخرة في أول صف، كل اللي بعدها في الصف ده 0، لأن مفيش طريق ليهم غير من الشمال، والشمال مقفول. جرّبتها: لو ملّيت أول صف وأول عمود 1 زي الأول، الإجابة تطلع 7 بدل 4.
- الحل الأنضف: بدل حالات خاصة للصف والعمود، كل خانة = فوق (لو موجود) + شمال (لو موجود)، والبداية 1.
- الصخرة الأول، قبل البداية: لو
(0, 0)نفسها صخرة، الإجابة 0 ([[1]]→ 0). - البداية: طريق واحد (إنك واقف).
- بدل
ifخاص للصف الأول: لو مفيش فوق، المساهمة 0. ده بيعالج الصخرة في أول صف لوحده من غير ما تفكّر فيها.
الخانات الرمادي صخور:
التعقيد: O(m · n).
لحد دلوقتي بنعدّ طرق. طب لو كل خانة ليها تكلفة، وعايز أرخص طريق؟
مثال محلول 3: Minimum Path Sum
grid أرقام موجبة. امشي من (0, 0) لـ (m - 1, n - 1) يمين أو تحت بس. إيه أقل مجموع للخانات اللي عدّيت عليها (شاملة البداية والنهاية)؟
الجديد هنا إن الـ transition = min + تكلفة الخانة، فأول صف وأول عمود بقوا مجموع تراكمي مش 1.
- الـ state:
dp[r][c]= أقل مجموع من(0, 0)لحد(r, c)شاملة الخانة. - الـ transition:
min(فوق، شمال) + grid[r][c]. - الـ base:
dp[0][0] = grid[0][0]. أول صف: من الشمال بس. أول عمود: من فوق بس. - ليه مش greedy؟ "روح للجار الأصغر" من
(0, 0)هيختار 2 (تحت) بدل 4، ويوصل لـ 12 (1، 2، 6، 1، 1، 1). الـ DP بيشوف إن الـ 4 بتفتح طريق أرخص بعدها.
- جدول منفصل عشان ما نعدّلش الـ input. ممكن تكتب في
gridنفسه وتوفّر الـ memory، بس قول للـ interviewer إنك بتعدّل الـ input. - مش ممكن تاخد
minمع خانة مش موجودة:dp[-1]=undefined، وMath.min(undefined, 5)=NaN. - الأرخص من الاتنين + تمن الخانة نفسها.
فوق الجدول: الـ dp. تحته: الـ grid الأصلي، والخانة الصفرا هي اللي بنضيف تمنها:
التعقيد: O(m · n) وقت، و O(m · n) أو O(n) بصف واحد أو O(1) لو كتبت في الـ grid.
في الـ grid، الرقمين كانوا صف وعمود. طب لو الرقمين مكان في string ومكان في string تاني؟
مثال محلول 4: Longest Common Subsequence
عندك اتنين strings. إيه طول أطول subsequence موجودة في الاتنين؟ (subsequence = حروف بنفس الترتيب، مش لازم جنب بعض.)
الجديد هنا تلات حاجات: الـ axes بقوا strings، والجدول (m + 1) × (n + 1) بصف وعمود للـ empty prefix، وظهر الـ قطري.
نفكّر فيها مع بعض (بالـ recipe)
- Brute force: كل subsequence من الأولى (2ᵐ) وتشوفها في التانية. مستحيل مع
m = 1000. - الـ state:
dp[i][j]= طول الـ LCS بين أولiحروف منtext1وأولjحروف منtext2. - الـ transition (آخر حرفين): بص على
text1[i - 1]وtext2[j - 1].
لو زي بعض: الحرف ده جزء من الـ LCS، والباقي من غيرهم:dp[i - 1][j - 1] + 1(القطري).
لو مختلفين: واحد فيهم مش في الـ LCS. يا نشيل حرف من الأولى (dp[i - 1][j]، فوق)، يا من التانية (dp[i][j - 1]، شمال)، وناخد الأكبر. - الـ base:
dp[0][j] = dp[i][0] = 0: string فاضي مالوش حاجة مشتركة. عشان كده الحجمm + 1وn + 1: الصف 0 والعمود 0 للـ empty prefix. - الترتيب:
iمن 1 لـmوjمن 1 لـn(شاملين). الإجابة:dp[m][n].
m + 1صف وn + 1عمود. الصف 0 والعمود 0 بيفضلوا 0 من الـfill، ودول الـ base cases.- من 1 لـ
mشاملة (<=)، لأنdp[m][n]هي الإجابة. - الـ off-by-one بتاع الفصل:
dp[i][j]بتتكلم عن أولiحروف، وآخرهمtext1[i - 1]. لو كتبتtext1[i]، هتقارن الحرف اللي بعده، وفي آخر لفةundefined. - القطري: الاتنين اتشالوا مع بعض لأنهم اتطابقوا.
- مش
+ 1هنا: مفيش حرف اتضاف للـ LCS.
الـ text1 على الصفوف و text2 على الأعمدة، والـ "" هو الـ empty prefix. الحرفين اللي بنقارنهم بيتلوّنوا:
نطلّع الـ subsequence نفسها: نرجع في الجدول
الجدول بيدّي الطول بس. عشان تطلّع الحروف، ابدأ من dp[m][n] وارجع ورا القرار اللي عمل كل خانة: لو الحرفين زي بعض، الحرف ده في الـ LCS ونروح قطري، وإلا نروح ناحية الخانة الأكبر (فوق أو شمال).
- بنقف أول ما نوصل للصف 0 أو العمود 0: مفيش حروف تانية.
- زي بعض = الخانة دي اتعملت من القطري + 1. ناخد الحرف ونروح قطري.
- مختلفين = الخانة اتعملت من الأكبر في فوق وشمال، فنمشي ناحيته. لو متساويين، أي واحد صح (وممكن يطلّع LCS مختلفة بنفس الطول).
- جمعنا الحروف من الآخر للأول، فنعكس.
التعقيد: O(m · n) وقت و memory. الرجوع O(m + n).
في LCS كان عندنا choice: نشيل حرف من هنا أو من هنا. طب لو عندنا 3 عمليات، ولكل واحدة تمن؟
مثال محلول 5: Edit Distance
حوّل word1 لـ word2 بأقل عدد عمليات. العمليات: insert حرف، delete حرف، replace حرف بحرف.
الجديد هنا إن كل عملية من التلاتة = خانة جارة (قطري، فوق، شمال)، وإن الـ base row/col بقوا i و j مش 0.
نفكّر فيها مع بعض (بالـ recipe)
- الـ state:
dp[i][j]= أقل عمليات تحوّل أولiحروف منword1لأولjحروف منword2. - الـ transition (آخر عملية على آخر حرف):
الحرفين زي بعض: مش محتاجين حاجة:dp[i - 1][j - 1].
Replaceword1[i - 1]بـword2[j - 1]: الاتنين اتظبطوا، فاضلdp[i - 1][j - 1](قطري) + 1.
Deleteword1[i - 1]: فاضل نحوّل أولi - 1لأولj:dp[i - 1][j](فوق) + 1.
Insertword2[j - 1]في الآخر: الحرف ده اتظبط، فاضل أولiلأولj - 1:dp[i][j - 1](شمال) + 1. - الـ base:
dp[i][0] = i(تمسحiحروف عشان توصل لـ "").dp[0][j] = j(تعملjinserts من ""). مش 0، لأن التحويل من أو لـ string فاضي ليه تمن. - الترتيب: صف صف. الإجابة:
dp[m][n]. الحجم:(m + 1) × (n + 1).
- الـ base row والـ column. لو سبتهم 0 من الـ fill،
""→"abc"هتطلع 0. - زي بعض = ببلاش. مش
min(...)هنا، ولا+ 1. - التلات جيران، كل واحد عملية. الـ
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) بصفين.
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).
هل تقدر تقسم الـ array لجزئين مجموعهم متساوي؟
الجديد هنا إن الـ state فيه capacity (مجموع)، وكل item مرة واحدة. وهنشوف إزاي الجدول بيتقلص لـ 1D، وليه الـ loop لازم ترجع لورا.
نفكّر فيها مع بعض (بالـ recipe)
- إعادة صياغة: لو المجموع الكلي
totalفردي، مستحيل. لو زوجي، السؤال بقى: "فيه subset مجموعهاtotal / 2؟". ده knapsack: الشنطة =target، وعايزين نملاها بالظبط. - الـ state:
dp[i][s]= هل فيه subset من أولiأرقام مجموعهاsبالظبط؟ - الـ transition: الرقم
x = nums[i - 1]يا سبناه:dp[i - 1][s]، يا أخدناه:dp[i - 1][s - x]. الاتنين من الصف اللي فوق، لأن كل رقم مرة واحدة. - الـ base:
dp[0][0] = true(صفر أرقام = مجموع 0)، والباقي false. - الإجابة:
dp[n][target]. الحجم:(n + 1) × (target + 1).
- Early return: فردي يبقى مستحيل، ومش محتاجين أي جدول.
target + 1عمود: المجاميع من 0 لـtargetشاملة.- Skip: نفس إجابة الصف اللي فوق.
- 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.
- صف واحد بدل الجدول:
O(target)memory. - لورا، و
s >= xعشانs - xما يبقاش سالب. والخانات الأصغر منxمش بتتلمس، وده صح: مش ممكن تتأثر بـx. - "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
عملات coins بعدد مالوش آخر. كام طريقة تعمل بيها المبلغ amount؟ 1 + 2 و 2 + 1 طريقة واحدة (combinations).
الجديد هنا إن ترتيب الـ loops بيغيّر الإجابة: coins برا = combinations، amounts برا = permutations. وكمان الـ loop لقدّام بقت صح لأن التكرار مسموح.
نفكّر فيها مع بعض (بالـ recipe)
- الـ state:
dp[a]= عدد الطرق تعملaبالعملات اللي اتعاملنا معاها لحد دلوقتي. - الـ transition: لما نضيف عملة
c: الطرق اللي فيهاcعلى الأقل مرة =dp[a - c]. فـdp[a] += dp[a - c]. - الـ base:
dp[0] = 1: طريقة واحدة تعمل 0، ما تاخدش حاجة. (زيdp[0] = 1في Climbing Stairs.) - ليه الـ coins برا؟ كده بنضيف العملات نوع نوع: الأول كل الطرق بالـ 1 بس، وبعدين نسمح بالـ 2، وهكذا. فأي combination بتتعدّ مرة واحدة بترتيب ثابت (الـ 1 قبل الـ 2 دايمًا)، و
2 + 1عمرها ما تتعدّ لوحدها. نفس فكرة الـ start index في الـ backtracking. - ليه لقدّام؟ عشان
dp[a - c]تبقى شاملة طرق فيهاcنفسها، يعنيcيتكرر. ده عكس الـ 0/1 knapsack بالظبط.
- عدّ = init بـ 0.
- من غيره كل حاجة تفضل 0، لأن كل طريقة في الآخر بتبدأ من 0.
- العملات برا: ده اللي بيخلّينا نعدّ combinations.
- من
cعشانa - c >= 0، و لقدّام عشان التكرار مسموح. +=مش=: بنضيف الطرق الجديدة اللي فيهاcعلى الطرق القديمة اللي من غيرها.
نفس الكود بترتيب loops معكوس
هنا لكل مبلغ بنجرّب كل عملة كـ آخر عملة، فـ 1 + 2 (آخرها 2) و 2 + 1 (آخرها 1) بيتعدّوا طريقتين. ده عدد permutations، وهو بالظبط حل Combination Sum IV (377).
| الـ loop البرّانية | الـ loop الجوّانية | بتعدّ | مسألة |
|---|---|---|---|
| coins | amounts لقدّام | combinations، والعملة تتكرر | 518 |
| amounts | coins | permutations (الترتيب فارق) | 377 |
| items | capacity لورا | كل item مرة واحدة (0/1) | 416، 494 |
التعقيد: O(amount × coins.length) وقت، و O(amount) memory.
شفنا 3 عائلات 2D. يلا نجمع كل الـ DP اللي شفناه في الفصلين في خريطة واحدة.
إزاي تعرف إنها DP، وأشهر الـ states
تلات أنواع أسئلة، وفيهم choices في كل خطوة، والـ subproblems بتتكرر:
- Optimal: أقل / أكبر (min cost، max profit، longest، shortest).
- Count: كام طريقة (number of ways، number of paths، number of combinations).
- Yes / No: هل ممكن (can you reach، can you partition، can you break).
ولو المسألة عايزة كل الإجابات نفسها، يبقى backtracking. ولو فيه choice بتقدر تثبت إنه الأحسن دايمًا، يبقى greedy أبسط.
| العيلة | الـ state | الـ transition | أمثلة |
|---|---|---|---|
| 1D prefix | dp[i] = answer for the first i | من i - 1 و i - 2 | 70، 198، 91 |
| 1D ending at i | dp[i] = best ending exactly at i | من كل j < i، والإجابة max | 300، 53 |
| 1D amount | dp[a] = best / ways for amount a | loop على الـ coins | 322، 279، 377 |
| 1D split point | dp[i] = can the prefix i be split | loop على مكان القطع j | 139 |
| Grid | dp[r][c] = answer up to cell (r, c) | فوق وشمال | 62، 63، 64، 221 |
| Two strings | dp[i][j] = prefixes i and j | قطري لو زي بعض، وإلا فوق / شمال | 1143، 72، 583 |
| 0/1 knapsack | dp[i][s] → dp[s], s backwards | skip / take من الصف اللي فوق | 416، 494 |
| Unbounded knapsack | dp[s], s forwards | skip / take من نفس الصف | 518، 322 |
| Interval | dp[l][r] = answer for s[l..r] | من intervals أصغر جواه | 516، 5 |
| State machine | dp[i][holding] = best on day i | buy / sell / rest | 309، 122 |
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] + 1dp[i - 1][j] + 1dp[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حروف لازمjinserts - عشان
jdeletes - عشان الـ 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.
تمرين: فكّر قبل ما تفتح
إيه طول أطول subsequence في s بتتقري زي ما هي من الناحيتين؟
تلميح 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 كفاية) واملا أول كام خانة بإيدك، وعلّم كل خانة بتبص على مين.
- Unique Pathsأول جدول: فوق + شمال.
- Unique Paths IIالـ base cases مش 1 على طول.
- Minimum Path Summin + تكلفة الخانة.
- Triangleنفس الفكرة على مثلث، واللف من تحت لفوق بيسهّلها.
- Maximal Squaregrid dp بـ min على 3 جيران (فوق، شمال، قطري).
- Longest Common Subsequenceأول two strings: (m + 1) × (n + 1) والقطري.
- Delete Operation for Two StringsLCS متنكّرة: الإجابة m + n - 2 × LCS.
- Longest Palindromic Subsequenceالتمرين اللي فوق: LCS مع العكس.
- Edit Distance3 عمليات = 3 جيران، والـ base i و j.
- Partition Equal Subset Sum0/1 knapsack، و 1D بـ loop لورا.
- Target Sumknapsack بالعدّ: حوّلها لـ "subset مجموعها كذا".
- Coin Change IIcombinations: الـ coins برا، و loop لقدّام.
وفي الآخر، الفصل كله في صفحة واحدة.
الخلاصة
| السؤال | الإجابة |
|---|---|
الجدول 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؟