Dynamic Programming 1overlapping subproblems · memoization · tabulation · 1D dp
في الـ backtracking كنا بنجرّب كل فروع الشجرة. هنا هنكتشف إن فروع كتير بتحسب نفس الحاجة. الـ DP مش سحر ومش معادلات بتتحفظ: هو recursion بتفتكر. لو نفس السؤال اتسأل مرتين، ما تحسبوش مرتين.
هتطلع من الفصل ده وإنت عارف
- تشوف بعينك ليه الـ recursion الساذجة exponential: نفس الـ subproblem بيتحسب مرات ومرات.
- تحوّل أي recursion لـ memoization (top-down)، وبعدين لـ tabulation (bottom-up)، وبعدين لـ O(1) memory لما ينفع.
- تكتب أي DP بـ recipe الخمس خطوات: الـ state بالكلام، الـ transition، الـ base cases، ترتيب اللفّ، والإجابة فين.
- تحل Climbing Stairs و Min Cost Climbing Stairs و House Robber و Coin Change و LIS و Word Break.
- تقفل باب الـ off-by-one: ليه
n + 1، وليهi <= n، وليهInfinity، وليهdp[0] = 1ساعات.
ليه DP؟ fib البطيء جدًا
في الفصل اللي فات الشجرة كانت بتجرّب كل الاحتمالات، وده كان مقبول لأن المطلوب الإجابات نفسها. دلوقتي خلّينا نشوف شجرة بتحسب رقم واحد، وهتلاقيها بتعيد نفسها كتير.
Fibonacci: كل رقم = مجموع الاتنين اللي قبله (0, 1, 1, 2, 3, 5, 8, …). يعني fib(n) = fib(n - 1) + fib(n - 2)، وأول كود بييجي في دماغك:
- الدالة صح رياضيًا، والـ bug مش في الصحة، في الوقت.
- ليه
n <= 1مشn === 1؟fib(2)بتناديfib(0). لو الـ base casen === 1بس،fib(0)هتنزل في السالب لحد stack overflow. وreturn nبتغطي الحالتين. - المشكلة: الـ call الأول جواه هيحسب
fib(n - 2)، والـ call التاني هيحسبها تاني من الصفر. الاتنين مش عارفين عن بعض حاجة.
اتفرّج على fib(5). الرقم تحت كل node = اللي رجّعته، والـ nodes الحمرا بتحسب حاجة اتحسبت قبل كده:
15 call عشان fib(5)، منهم 9 تكرار. والكارثة بتكبر بسرعة (عدد الـ calls بيتضرب في 1.6 تقريبًا مع كل زيادة في n). جرّبتها في node:
| n | عدد الـ calls | الوقت التقريبي |
|---|---|---|
| 5 | 15 | لحظة |
| 40 | 331,160,281 | حوالي 2.4 ثانية |
| 50 | 40,730,022,147 | حوالي 5 دقايق |
مع إن fib(50) محتاجة 51 قيمة بس، من fib(0) لـ fib(50). الباقي كله تكرار.
شرطين عشان المسألة تبقى DP
- Optimal substructure: الإجابة الكبيرة مبنية من إجابات أصغر.
fib(5)منfib(4)وfib(3). - Overlapping subproblems: المسائل الصغيرة بتتكرر.
fib(3)اتطلبت مرتين وfib(2)تلات مرات. في merge sort مثلًا كل نص مختلف، فالـ memo مش هيفيد.
يعني الـ DP هو نفس شجرة الـ backtracking، بس كل node بتتحسب مرة واحدة.
طب إزاي تعرف من كلام المسألة إنها DP أصلًا؟
إزاي تعرفه من المسألة
المسألة بتطلب رقم واحد (عدد، أقل، أكبر، آه ولا لأ)، وجواها choices في كل خطوة بتأثر على اللي بعدها. والـ key test: تقدر تكتب الإجابة على n من إجابات inputs أصغر؟
| Backtracking | DP | Greedy | |
|---|---|---|---|
| المطلوب | كل الإجابات نفسها | رقم واحد: عدد أو أحسن قيمة | رقم واحد، وفيه choice واضح إنه الأحسن دايمًا |
| بيجرّب إيه | كل فروع الشجرة | كل state مختلفة، مرة واحدة | فرع واحد بس |
| الوقت | exponential | عدد الـ states × شغل كل state | غالبًا O(n log n) أو O(n) |
| الخطر | بطيء لو n كبيرة | تختار state غلط | ممكن يطلع غلط (هتشوف Coin Change) |
flowchart TD
A["Problem asks for ONE number: count, min, max, true/false?"] -- "no: list all answers" --> B["Backtracking"]
A -- "yes" --> C{"Can answer(n) be built from answers of smaller inputs?"}
C -- "no" --> D["Probably greedy, two pointers, or a formula"]
C -- "yes" --> E{"Do the same smaller inputs repeat?"}
E -- "no" --> F["Plain recursion / divide and conquer"]
E -- "yes" --> G["DP: memo or table"]
السؤال اللي بيحسمها: "الإجابة على n، أقدر أكتبها من إجابات أصغر؟"
عرفنا إمتى. يلا نبدأ بالإزاي: أسهل تحويل، نضيف ذاكرة للـ recursion نفسها.
الخطوة 1: Memoization (top-down)
خد الـ recursion زي ما هي وضيف لها ذاكرة: قبل ما تحسب، اسأل "حسبتها قبل كده؟". لو آه رجّعها على طول، لو لأ احسبها واكتبها ورجّعها.
- الـ default parameter بيعمل Map جديد بس في الـ call الخارجي. الـ calls اللي جوه بتبعت نفس الـ Map، فكلهم بيكتبوا في نفس الورقة.
- ليه
hasمشif (memo.get(n))؟ لو القيمة المحفوظة 0، الـ 0 falsy، فهتتحسب تاني. في مسائل كتير الـ 0 قيمة عادية، والـ memo بيبطل يشتغل من غير ما تاخد بالك: جرّبتها على دالة كل قيمها 0،n = 25عملت 242,785 call بدل حوالي 50. - نفس سطر الـ recursion القديم، بس بنبعت الـ memo.
- نكتب قبل ما نرجّع. أكتر سطر بيتنسي، ومن غيره كأننا ما عملناش حاجة.
نفس fib(5) ومعاها الـ memo. الـ nodes الخضرا رجعت من الـ memo على طول، من غير ولا call تحتها:
9 calls بدل 15، وكل n بتتحسب مرة: حوالي 2n call، يعني O(n). fib(50) بقت 99 call بدل 40 مليار. والـ memory O(n) (الـ Map والـ stack).
n. في JS الـ stack بيستحمل حوالي 10 آلاف call (بيختلف حسب البيئة). مع n = 10⁵ هيضرب Maximum call stack size exceeded رغم إن الـ complexity كويسة.
طب نقدر نستغنى عن الـ recursion خالص، ونبني الإجابات من تحت لفوق؟
الخطوة 2: Tabulation (bottom-up)
في الـ memo بننزل من fib(n) للـ base cases وبعدين الإجابات بتطلع. ليه ما نبدأش من تحت على طول؟ نعمل array، نملا الـ base cases، ونطلع cell by cell لحد n.
- لو
n = 0من غيره، سطر 5 هيكتب برا الـ array. JS بتكبّرها لوحدها والإجابة تطلع صح بالصدفة، بس في C++ ده out of bounds. - ليه
n + 1؟ أهم نقطة في الفصل. عايزينdp[n]، والـ indices من 0، فلازمn + 1خانة. بـnew Array(n)هتبقىdp[n]=undefined، وundefined + 5=NaNمن غير error. نفس غلطة FizzBuzz: "لحد n شاملة". - الـ base cases: الحاجات اللي عارفينها من غير حساب.
i = 2لأن 0 و 1 اتملوا.<=لأنdp[n]هي الإجابة: بـ<هتفضل 0. و من الصغير للكبير لأنdp[i]محتاجة اللي قبلها جاهز.- نفس الـ recursion، بس بنقرا من الـ array بدل ما ننادي دالة.
الخانة الصفرا بتتملي دلوقتي، والتركوازي هما الخانتين اللي بنقرا منهم:
التعقيد: O(n) وقت و O(n) memory، ومفيش recursion فمفيش stack overflow.
بص على الـ animation: كل خانة محتاجة آخر اتنين بس. محتاجين الـ array كلها؟
الخطوة 3: O(1) memory
كل اللي قبل آخر خانتين عمرنا ما رجعنالهم، فمتغيرين كفاية.
prev1=dp[i - 1]وprev2=dp[i - 2]. عندi = 2هما 1 و 0.- الترتيب هنا كل حاجة. لو بدأت بـ
prev1 = cur، الـprev2هتاخدcurهي كمان والاتنين يبقوا نفس الرقم. اسأل: "مين محتاج القيمة القديمة؟" وحرّكه الأول. - بعد آخر لفة
prev1 = fib(n). لو رجّعتprev2هترجّعfib(n - 1).
الخانات الباهتة "اتنسيت": موجودة في الرسمة بس، الكود مش محتفظ بيها:
| النسخة | الوقت | الـ memory | إمتى |
|---|---|---|---|
| Recursion ساذجة | O(1.6ⁿ) | O(n) stack | على الورق بس، عشان تفهم الـ transition. |
| Memo (top-down) | O(n) | O(n) | لما الـ recursion أسهل في التفكير، أو مش كل الـ states محتاجة تتحسب. |
| Table (bottom-up) | O(n) | O(n) | الـ default في الانترفيو: مفيش stack overflow، والترتيب واضح. |
| متغيرين | O(n) | O(1) | لما كل خانة تعتمد على عدد ثابت قبلها. كتحسين بعد ما الـ table يشتغل. |
كده الأدوات معاك. فاضل الأهم: إزاي تفكّر في مسألة DP جديدة عمرك ما شفتها؟
الـ recipe: خمس خطوات لأي DP
كل مسألة في الفصل ده والجاي هتتحل بالخمس أسئلة دول، بالترتيب. اكتبهم بالكلام قبل الكود. لو مش قادر تكتب خطوة 1 في جملة واضحة، الكود هيطلع غلط.
| الخطوة | السؤال | في fib |
|---|---|---|
| 1. الـ state | dp[i] معناها إيه بالظبط؟ جملة كاملة. | dp[i] = رقم Fibonacci رقم i. |
| 2. الـ transition | إزاي أحسب dp[i] من states أصغر؟ فكّر في آخر قرار. | dp[i] = dp[i - 1] + dp[i - 2] |
| 3. الـ base cases | أصغر states أعرفها من غير حساب؟ وهل الـ transition بيقرا index سالب؟ | dp[0] = 0، dp[1] = 1، والـ loop من 2. |
| 4. ترتيب اللفّ | لِف بطريقة تخلّي كل اللي محتاجه جاهز قبله. | i من 2 لـ n طالع. |
| 5. الإجابة فين | dp[n]؟ dp[n - 1]؟ أكبر قيمة في الـ array؟ | dp[n] |
0 لـ n شاملة، يبقى n + 1. لو الـ states indices في array طولها n، يبقى n. ما تحفظش "دايمًا n + 1"، اسأل: "أكبر index هقراه كام؟" وزوّد 1.
يلا نطبّق الـ recipe على أول مسألة حقيقية: Climbing Stairs.
مثال محلول 1: Climbing Stairs
سلم فيه n درجة. في كل حركة بتطلع درجة أو درجتين. بكام طريقة مختلفة توصل للدرجة n؟
نفكّر فيها مع بعض (بالـ recipe)
- Brute force: backtracking يجرّب كل التسلسلات، وعددها exponential. مع
n = 45الإجابة 1,836,311,903، مستحيل نعدّهم واحدة واحدة. - الـ state:
dp[i]= عدد الطرق اللي توصّلك للدرجةiبالظبط. - الـ transition (آخر قرار): آخر حركة يا درجة (كنت على
i - 1) يا درجتين (كنت علىi - 2)، والنوعين مختلفين تمامًا. فـdp[i] = dp[i - 1] + dp[i - 2]. أيوه، هي fib. - الـ base cases:
dp[0] = 1وdp[1] = 1. ليهdp[0] = 1مش 0؟ "تفضل على الأرض" = طريقة واحدة: ما تعملش حاجة. ولو 0،dp[2]هتطلع 1 والصح 2 (1+1 و 2). اختبر الـ base case دايمًا بأصغر حالة بعده. - الترتيب: من 2 لـ
n. الإجابة:dp[n]. الحجم:n + 1.
n + 1: من الأرض (0) للدرجةn. والـ constraints بتقولn >= 1، فسطر 4 آمن.- الطريقة الفاضية. مش رقم "طبيعي"، بس هو اللي بيخلّي الـ transition صح عند
i = 2. i <= n، لأنdp[n]هي الإجابة.- بنجمع لأن المطلوب عدد طرق. لو المطلوب "أقل عدد حركات" كنا هناخد
min+ 1. نوع السؤال بيحدد العملية: عدد = sum، أحسن = min أو max.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| n = 1 | 1 | الـ loop مش بتلف، والإجابة من الـ base case. |
| n = 2 | 2 | بتختبر dp[0] = 1. |
| n = 45 | 1836311903 | أقصى n: الـ recursion الساذجة مش هتلحق. |
التعقيد: O(n) وقت، و O(n) أو O(1) memory بالمتغيرين.
هنا كنا بنعدّ طرق. طب لو كل درجة ليها تمن، وعايز الأرخص؟
مثال محلول 2: Min Cost Climbing Stairs
كل درجة i ليها تمن cost[i] بتدفعه لما تطلع منها (درجة أو درجتين). تبدأ من الدرجة 0 أو 1 ببلاش. السطح هو بعد آخر درجة. إيه أقل تكلفة توصّلك للسطح؟
الجديد هنا إن الـ transition بياخد min بدل الجمع، وإن الإجابة مش عند آخر index: السطح هو n.
نفكّر فيها مع بعض (بالـ recipe)
- فين السطح؟ الدرجات من 0 لـ
n - 1، والسطح "الدرجة رقمn". الوقوف على آخر درجة مش معناه إنك وصلت. - الـ state:
dp[i]= أقل تكلفة توصّلك تقف على الدرجةi(من غير ما تدفع تمنها لسه). - الـ transition: يا من
i - 1ودفعتcost[i - 1]، يا منi - 2ودفعتcost[i - 2]، وناخد الأرخص. - الـ base cases:
dp[0] = dp[1] = 0، البداية ببلاش. - الترتيب: من 2 لـ
n. الإجابة:dp[n]. الحجم:n + 1.
n + 1: الدرجات + السطح. والـfill(0)بيعمل الـ base cases لوحده.- بندفع تمن الدرجة اللي طلعنا منها. لما
i = nمفيشcost[n]، وده صح: السطح ببلاش. - أقل تكلفة =
min. لو كتبتmaxالكود هيشتغل عادي ويطلّع أغلى طريق. - السطح.
dp[n - 1]تكلفة الوقوف على آخر درجة، ولسه ما دفعتش تمنها.
صف cost فوق و dp تحت، وفيها خانة زيادة: السطح:
التعقيد: O(n) وقت، و O(n) أو O(1) memory.
في المثالين اللي فاتوا القرار كان "جيت منين". طب لو القرار "آخد ولا أسيب"، والاختيار بيمنع اللي جنبه؟
مثال محلول 3: House Robber
بيوت جنب بعض، وفي كل بيت فلوس nums[i]. مينفعش تسرق بيتين جنب بعض. إيه أكبر مبلغ تقدر تاخده؟
الجديد هنا إن الـ transition = take or skip، وإن الـ state "أول i بيوت" بيدّينا حالة فاضية ببلاش.
نفكّر فيها مع بعض (بالـ recipe)
- حلول بتبان صح وهي غلط: "الزوجي أو الفردي": 6 + 3 + 4 = 13 و 2 + 9 + 1 = 12، والصح 16 (سبنا بيتين ورا بعض). محتاجين نجرّب كل الـ choices من غير تكرار.
- الـ state:
dp[i]= أكبر مبلغ من أولiبيوت (من 0 لـi - 1). - الـ transition (آخر قرار): البيت
i - 1يا سبناه:dp[i - 1]، يا سرقناه فجاره ممنوع:dp[i - 2] + nums[i - 1]. وناخد الأكبر. - الـ base cases:
dp[0] = 0(مفيش بيوت)،dp[1] = nums[0]. - الترتيب: من 2 لـ
n. الإجابة:dp[n]. الحجم:n + 1.
dp[1] = max(nums[0], nums[1])، وده بيقع لو فيه بيت واحد. "أول i بيوت" بيدّيك dp[0] = 0 مجانًا. الـ trade-off: البيت بتاع dp[i] هو nums[i - 1].
dp[0] = 0من الـfill: صفر بيوت = صفر فلوس.- بيت واحد على الأقل حسب الـ constraints. لو سمحت بـ array فاضية، اكتب
if (n === 0) return 0الأول. - الـ
i - 1هنا هو الـ off-by-one بتاع المسألة. بـnums[i]هتاخد البيت اللي بعده، وفي آخر لفةnums[n]=undefinedوالإجابةNaN. - أكبر مبلغ =
max.
وزي fib، كل خانة محتاجة آخر اتنين بس، فينفع O(1):
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [5] | 5 | الـ loop مش بتلف. |
| [2, 1, 1, 2] | 4 | الأحسن بيسيب بيتين ورا بعض. |
| [6, 2, 3, 9, 4, 1] | 16 | مثال الـ animation. |
التعقيد: O(n) وقت، O(n) أو O(1) memory.
لحد دلوقتي كل خانة بتبص على آخر خانتين بس. طب لو الـ choices كتير، وكل choice بيرجّعك لخانة مختلفة؟
مثال محلول 4: Coin Change
عندك أنواع عملات coins، ومن كل نوع عدد مالوش آخر. إيه أقل عدد عملات يعمل المبلغ amount بالظبط؟ لو مستحيل رجّع -1.
الجديد هنا إن الـ transition جواه loop على كل الـ coins، وإن الـ init بقى Infinity، وإن الـ greedy اللي بيبان منطقي بيقع.
ليه الـ greedy بيقع هنا؟
"خد أكبر عملة تنفع وكرر" بتشتغل مع الفكة المصرية (200، 100، 50…) عشان متصممة كده. بس مع [1, 3, 4] و 6:
| الطريقة | الاختيارات | عدد العملات |
|---|---|---|
| Greedy (الأكبر الأول) | 4 → فاضل 2 → 1 → فاضل 1 → 1 | 3 |
| الصح | 3 + 3 | 2 |
الـ 4 شكلها أحسن choice دلوقتي، بس بتسيبك في 2. الـ greedy بياخد قرار ومش بيرجع فيه، فمحتاجين نجرّب كل عملة كآخر عملة.
نفكّر فيها مع بعض (بالـ recipe)
- الـ state:
dp[a]= أقل عدد عملات يعمل المبلغaبالظبط. - الـ transition (آخر عملة): لو آخر عملة
c، قبلها كان معاناa - c. فـdp[a] = min(dp[a - c] + 1)على كلc <= a. - الـ base case:
dp[0] = 0. - الـ init:
Infinity= "لسه مش عارفين نعمله". بـ 0:min(0, أي حاجة) = 0فكله يفضل 0. بـ -1:min(-1, 3) = -1فالـ -1 تكسب دايمًا. الـInfinityبتخسر أي مقارنة، وInfinity + 1لسهInfinity. - الترتيب:
aمن 1 لـamount. الإجابة:dp[amount]أو -1. الحجم:amount + 1.
- ناس بتستخدم
amount + 1بدلInfinity: مستحيل تحتاج أكتر منamountعملة. الاتنين صح، وInfinityأوضح. - الـ base case الوحيد، وكل مبلغ في الآخر بيتبني عليه.
c <= aعشانa - cما يبقاش سالب. ولوdp[a - c]لسهInfinity، المقارنة عمرها ما هتبقى true، فالمبالغ المستحيلة مش بتأثر.- لو نسيت التحويل هترجّع
Infinityوالمطلوب-1.
الـ ∞ = "لسه مش عارفين نعمله". الخانة التركوازي هي dp[a - c] اللي بنبني عليها:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [1], 0 | 0 | الـ loop مش بتلف. |
| [2], 3 | -1 | dp[3] بتفضل Infinity. |
| [1, 3, 4], 6 | 2 | الـ greedy بيطلّع 3. |
| [186, 419, 83, 408], 6249 | 20 | عملات كبيرة ومفيش 1: أغلب الخانات Infinity. |
التعقيد: O(amount × coins.length) وقت، و O(amount) memory.
في كل اللي فات الإجابة كانت في آخر خانة. فيه مسائل الإجابة فيها ممكن تبقى في أي خانة.
مثال محلول 5: Longest Increasing Subsequence
إيه طول أطول subsequence متزايدة بشكل صارم؟ الـ subsequence يعني تشيل عناصر من غير ما تغيّر ترتيب الباقي (مش لازم يكونوا جنب بعض).
الجديد هنا إن الـ state "بتخلص عند i"، فالإجابة max(dp) مش آخر خانة، والحجم n مش n + 1.
نفكّر فيها مع بعض (بالـ recipe)
- Brute force: كل subsequence = subset، يعني 2ⁿ. مع
n = 2500مستحيل. - محاولة أولى: "
dp[i]= أطول واحدة في أولiعناصر". المشكلة: عشان تضيفnums[i]لازم تعرف آخر عنصر في الـ sequence، والـ state ده مش بيقولك. لما الـ transition ما يتكتبش، غيّر الـ state. - الـ state الصح:
dp[i]= طول أطول increasing subsequence بتخلص عندnums[i]. كده آخر عنصر معروف. - الـ transition: قبل
nums[i]كان فيهnums[j]أصغر منه (j < i)، أو مفيش. فـdp[i] = 1 + max(dp[j])، ولو مفيشjيبقى 1. - Base: كله 1. الحجم:
n، لأن الـ states indices من 0 لـn - 1. الإجابة:maxعلى كل الـ dp، لأن الـ LIS ممكن تخلص عند أي عنصر.
- الـ 1 دي الـ base case و "مفيش j" في نفس الوقت.
best = 1مش 0، عشان لوn = 1الإجابة 1.i < nمش<=، لأن الـ states هنا indices لحدn - 1. قارن بـ Climbing Stairs: هناك الـ states لحدn. الفرق جاي من خطوة 1.<مش<=، عشان strictly increasing. بـ<=،[7, 7, 7]هتطلع 3.- بديل إنك تعمل
Math.max(...dp)في الآخر.
i بيلف، و j بيعدّي على اللي قبله. الأخضر = ينفع نمد منه، والأحمر = لأ:
التعقيد: O(n²) وقت و O(n) memory. مع n = 2500 ده حوالي 3 مليون عملية، يعدّي.
احتفظ بـ tails: tails[k] = أصغر عنصر ممكن تخلص بيه increasing subsequence طولها k + 1. الـ array دي دايمًا مترتبة، فلكل عنصر تعمل binary search على أول خانة أكبر منه أو بتساويه وتحطه مكانها (أو في الآخر). طول tails هو الإجابة، بس tails نفسها مش الـ LIS.
قارنته بنسخة الـ O(n²) على 300 array عشوائية، ونفس الإجابات.
آخر مثال: dp من true/false، والسؤال فيه "أقطع فين".
مثال محلول 6: Word Break
عندك string s وقاموس كلمات. هل تقدر تقطّع s لكلمات كلها من القاموس؟ (نفس الكلمة مسموح تتكرر.)
الجديد هنا إن الـ dp بـ true/false، والـ transition بيدوّر على مكان القطع j.
نفكّر فيها مع بعض (بالـ recipe)
- Brute force: backtracking يجرّب كل كلمة في البداية ويكمّل. مع
"aaaa…ab"و["a", "aa", "aaa"]بينفجر، و "هل الباقي من index 5 بيتقطّع؟" بيتسأل مرات كتير: overlapping subproblems. - الـ state:
dp[i]= هل أولiحروف (s.slice(0, i)) بيتقطّعوا؟ - الـ transition (آخر كلمة): آخر كلمة بتبدأ عند
jوبتخلص عندi. الشرط:dp[j]true، وs.slice(j, i)في القاموس. - الـ base case:
dp[0] = true: الـ string الفاضي = صفر كلمات. من غيره مفيش أي true، لأن أول كلمة بتبدأ عند 0. - الترتيب:
iمن 1 لـn. الإجابة:dp[n]. الحجم:n + 1.
- Set بدل
includesاللي بتلف على القاموس كله كل مرة. - الـ base case اللي كل true بتتبني عليه.
j= بداية آخر كلمة.j = 0يعني الـ prefix كله كلمة واحدة.s.slice(j, i)منjلحدi - 1، والـiمش داخل، وده بالظبط الـ prefix بتاعdp[i]. وdp[j]الأول: لو false، الـ&&بتقف قبل الـ slice.- طريقة واحدة كفاية. الـ
breakتوفير بس.
صف s فوق والـ dp تحت (فيها dp[0] للـ prefix الفاضي). الجزء الأزرق = آخر كلمة لقيناها:
التعقيد: O(n²) زوج (i, j)، وكل slice لحد O(n): O(n³) worst case، ومع n = 300 يعدّي. تحسين: j تبدأ من i - maxWordLength.
شفت كام مكان ممكن الـ off-by-one يوقعك فيه؟ يلا نجمعهم.
غلطات مشهورة
أغلب غلطات الـ DP في الحدود مش في الفكرة، وكلها بتشتغل من غير error وتطلّع رقم غلط.
1. حجم الـ array n بدل n + 1
2. i < n بدل i <= n
نفس غلطة FizzBuzz. القاعدة جاية من الـ state: لو الـ states لحد n شاملة يبقى <=، ولو indices لحد n - 1 (زي LIS) يبقى <.
3. Base case غلط
اختبر الـ base case بإيدك على أصغر حالة بعده.
4. Init غلط في مسائل الـ min
min: Infinity. max: -Infinity (أو 0 لو مفيش سالب). عدّ: 0 والـ base غالبًا 1.
5. Memo check بقيمة ممكن تبقى 0
6. الإجابة مش دايمًا في آخر خانة
LIS: max(dp). Min Cost Climbing Stairs: dp[n] (السطح) مش dp[n - 1]. خطوة 5 في الـ recipe مش رفاهية.
7. Greedy بدل DP
لو "خد الأحسن دلوقتي" شكلها صح، دوّر على counterexample صغير الأول: [1, 3, 4] و 6، أو [2, 1, 1, 2] في House Robber. لو لقيت واحد، يبقى DP.
يلا نختبر الكلام ده.
اختبر نفسك
إيه اللي بيخلّي الـ memo يحوّل fib من exponential لـ O(n)؟
- إنه بيستخدم Map بدل array
- كل
fib(k)بتتحسب مرة واحدة، وأي طلب تاني ليها بيرجع من الذاكرة في O(1) - إنه بيلغي الـ recursion
- إنه بيحسب من تحت لفوق
فيه n + 1 state بس، وكل واحدة بتتحسب مرة بـ O(1). الـ memo لسه recursion، اللي بيلغيها الـ tabulation.
في Climbing Stairs كتبت new Array(n) و i <= n. إيه اللي هيحصل مع n = 3؟
- هيضرب error: index out of range
- JS هتكبّر الـ array لوحدها لما تكتب في
dp[3]، والإجابة تطلع صح بالصدفة، بس الكود مكسور في أي لغة تانية - هترجّع 0
- هترجّع
NaN
JS مش بتعمل bounds check. في C++ أو Java ده crash أو قراءة memory غلط. اكتب n + 1 عشان الكود يقول اللي إنت قاصده.
في Coin Change، ليه fill(Infinity) مش fill(0)؟
- عشان الـ performance
- عشان الأرقام ممكن تبقى سالبة
- لأننا بناخد
min، والـ 0 هيكسب أي مقارنة للأبد، وInfinityبيخسر أي مقارنة مع رقم حقيقي - مش فارقة
الـ init = "أوحش قيمة" بالنسبة للعملية: Infinity للـ min، و -Infinity للـ max. والـ base case هو الاستثناء.
في LIS، nums = [3, 4, 1] فـ dp = [1, 2, 1]. الإجابة كام؟
- 1، عشان
dp[n - 1] = 1 - 2، عشان الإجابة أكبر قيمة في
dp - 3
- 4
dp[i] = "أطول واحدة بتخلص عند i"، والـ LIS هنا بتخلص عند الـ 4.
في Word Break، لو نسيت dp[0] = true؟
- هيشتغل عادي
- هيضرب error
- هيرجّع false دايمًا، لأن أول كلمة بتبدأ عند 0 ومحتاجة
dp[0]true - هيرجّع true دايمًا
كل true لازم تيجي من true قبلها، والـ base case هو أول true.
تمرين: فكّر قبل ما تفتح
نفس House Robber، بس البيوت في دايرة: أول بيت وآخر بيت جيران.
تلميح 1
المشكلة كلها في أول وآخر بيت: مينفعش ياخدوا الاتنين. يعني يا أول بيت مش مسروق، يا آخر بيت مش مسروق.
تلميح 2
شيل أول بيت: الدايرة تبقى خط. شيل آخر بيت: برضه خط. احسب House Robber العادي على الاتنين وخد الأكبر. وخلي بالك من بيت واحد بس.
الحل
مع بيت واحد الـ slice الاتنين فاضيين والإجابة تطلع 0، عشان كده الـ if. جرّبته على الأمثلة التلاتة وعلى [7] (طلعت 7).
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
في كل مسألة اكتب الخمس خطوات كـ comments قبل الكود. ولو اتزنقت: recursion ساذجة، وبعدين memo، وبعدين table.
- Fibonacci Numberاكتبه بالأربع نسخ: ساذج، memo، table، متغيرين.
- N-th Tribonacci Numberfib بتلات خانات: تلات base cases وتلات متغيرين.
- Climbing Stairsأول "عدد طرق"، وليه
dp[0] = 1. - Min Cost Climbing Stairsأول min، والسطح
nمشn - 1. - House Robberأول take/skip.
- House Robber IIالتمرين اللي فوق: قسّم الحالة لحالتين أسهل.
- Delete and EarnHouse Robber متنكّرة. لو شفتها لوحدك يبقى فهمت.
- Coin Changeloop على الـ choices، و Infinity، والـ greedy اللي بيقع.
- Perfect SquaresCoin Change والعملات هي المربعات 1، 4، 9…
- Combination Sum IVعدد طرق والترتيب فارق. هتفهم ليه في Coin Change II في الفصل الجاي.
- Longest Increasing Subsequencestate "بتخلص عند i"، والإجابة max.
- Word Breakdp من true/false، و "آخر كلمة بتبدأ فين".
- Decode WaysClimbing Stairs بشروط، والـ '0' فخ.
وفي الآخر، الفصل كله في صفحة واحدة.
الخلاصة
| المسألة | الـ state | الـ transition | base | الإجابة |
|---|---|---|---|---|
| Climbing Stairs | طرق الوصول لدرجة i | dp[i-1] + dp[i-2] | dp[0]=dp[1]=1 | dp[n] |
| Min Cost Stairs | أقل تكلفة للوقوف على i | min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) | dp[0]=dp[1]=0 | dp[n] |
| House Robber | أحسن مبلغ من أول i بيوت | max(dp[i-1], dp[i-2]+nums[i-1]) | dp[0]=0, dp[1]=nums[0] | dp[n] |
| Coin Change | أقل عملات للمبلغ a | min over c of dp[a-c]+1 | dp[0]=0, rest ∞ | dp[amount] or -1 |
| LIS | أطول increasing بتخلص عند i | 1 + max dp[j], j<i, nums[j]<nums[i] | all 1 | max(dp) |
| Word Break | أول i حروف بيتقطّعوا؟ | any j: dp[j] and s[j..i) in dict | dp[0]=true | dp[n] |
| السؤال | الإجابة |
|---|---|
| Memo ولا table؟ | نفس الـ complexity. الـ table أأمن من stack overflow وأسهل تحوّله لـ O(1). |
n ولا n + 1؟ | أكبر index هتقراه + 1. |
< ولا <=؟ | لو آخر state هي n نفسها: <=. |
| الـ init إيه؟ | عدّ: 0. min: Infinity. max: -Infinity. yes/no: false. والـ base بعده. |
| الإجابة فين؟ | غالبًا dp[n]. لو الـ state "بتخلص عند i": max(dp). |
الفصل الجاي: كل الـ states هنا كانت رقم واحد dp[i]. بس فيه مسائل الإجابة بتعتمد على حاجتين: مكانك في grid (صف وعمود)، أو مكانك في string أول وفي string تاني، أو أنهي عنصر وقد إيه سعة الشنطة. ساعتها الـ state بيبقى dp[i][j] والـ table بقى جدول. ده Dynamic Programming 2، والـ recipe والـ base cases والـ n + 1 هيتنقلوا هناك زي ما هم، بس في بعدين.