Dynamic Programming 1overlapping subproblems · memoization · tabulation · 1D dp

في الـ backtracking كنا بنجرّب كل فروع الشجرة. هنا هنكتشف إن فروع كتير بتحسب نفس الحاجة. الـ DP مش سحر ومش معادلات بتتحفظ: هو recursion بتفتكر. لو نفس السؤال اتسأل مرتين، ما تحسبوش مرتين.

قبله: Recursion و Backtracking بيمهّد لـ: Dynamic Programming 2

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

  • تشوف بعينك ليه الـ 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)، وأول كود بييجي في دماغك:

  1. الدالة صح رياضيًا، والـ bug مش في الصحة، في الوقت.
  2. ليه n <= 1 مش n === 1؟ fib(2) بتنادي fib(0). لو الـ base case n === 1 بس، fib(0) هتنزل في السالب لحد stack overflow. و return n بتغطي الحالتين.
  3. المشكلة: الـ call الأول جواه هيحسب fib(n - 2)، والـ call التاني هيحسبها تاني من الصفر. الاتنين مش عارفين عن بعض حاجة.

اتفرّج على fib(5). الرقم تحت كل node = اللي رجّعته، والـ nodes الحمرا بتحسب حاجة اتحسبت قبل كده:

15 call عشان fib(5)، منهم 9 تكرار. والكارثة بتكبر بسرعة (عدد الـ calls بيتضرب في 1.6 تقريبًا مع كل زيادة في n). جرّبتها في node:

nعدد الـ callsالوقت التقريبي
515لحظة
40331,160,281حوالي 2.4 ثانية
5040,730,022,147حوالي 5 دقايق

مع إن fib(50) محتاجة 51 قيمة بس، من fib(0) لـ fib(50). الباقي كله تكرار.

تشبيه حد سألك "37 × 24 بكام؟". حسبتها في ورقة: 888. بعد دقيقة سألك نفس السؤال. مش هتحسب من الأول، هتبص في الورقة. الـ DP = تكتب كل نتيجة في ورقة أول ما تحسبها، وتبص في الورقة قبل ما تحسب أي حاجة. الورقة دي اسمها memo أو dp table.

شرطين عشان المسألة تبقى DP

يعني الـ DP هو نفس شجرة الـ backtracking، بس كل node بتتحسب مرة واحدة.

طب إزاي تعرف من كلام المسألة إنها DP أصلًا؟

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

المسألة بتطلب رقم واحد (عدد، أقل، أكبر، آه ولا لأ)، وجواها choices في كل خطوة بتأثر على اللي بعدها. والـ key test: تقدر تكتب الإجابة على n من إجابات inputs أصغر؟

لما تشوف: number of waysminimum cost / minimum number ofmaximum profit / sum is it possible / can youlongest / shortest subsequence1 or 2 steps take it or skip itcan't take two adjacentunlimited coins
ومش هو غالبًا لو: return ALL combinations (backtracking)shortest path in an unweighted grid (BFS)sorted + pair sum (two pointers)
BacktrackingDPGreedy
المطلوبكل الإجابات نفسهارقم واحد: عدد أو أحسن قيمةرقم واحد، وفيه 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 زي ما هي وضيف لها ذاكرة: قبل ما تحسب، اسأل "حسبتها قبل كده؟". لو آه رجّعها على طول، لو لأ احسبها واكتبها ورجّعها.

  1. الـ default parameter بيعمل Map جديد بس في الـ call الخارجي. الـ calls اللي جوه بتبعت نفس الـ Map، فكلهم بيكتبوا في نفس الورقة.
  2. ليه has مش if (memo.get(n))؟ لو القيمة المحفوظة 0، الـ 0 falsy، فهتتحسب تاني. في مسائل كتير الـ 0 قيمة عادية، والـ memo بيبطل يشتغل من غير ما تاخد بالك: جرّبتها على دالة كل قيمها 0، n = 25 عملت 242,785 call بدل حوالي 50.
  3. نفس سطر الـ recursion القديم، بس بنبعت الـ memo.
  4. نكتب قبل ما نرجّع. أكتر سطر بيتنسي، ومن غيره كأننا ما عملناش حاجة.

نفس fib(5) ومعاها الـ memo. الـ nodes الخضرا رجعت من الـ memo على طول، من غير ولا call تحتها:

9 calls بدل 15، وكل n بتتحسب مرة: حوالي 2n call، يعني O(n). fib(50) بقت 99 call بدل 40 مليار. والـ memory O(n) (الـ Map والـ stack).

خلي بالك من عمق الـ stack الـ top-down لسه recursion، وعمقها 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.

تشبيه الـ top-down زي إنك تسأل "أنا في الدور الكام؟"، فتسأل اللي تحتك، وهو يسأل اللي تحته لحد الأرضي. الـ bottom-up إنك تطلع السلم من الأرضي وتعدّ: 1، 2، 3.
  1. لو n = 0 من غيره، سطر 5 هيكتب برا الـ array. JS بتكبّرها لوحدها والإجابة تطلع صح بالصدفة، بس في C++ ده out of bounds.
  2. ليه n + 1؟ أهم نقطة في الفصل. عايزين dp[n]، والـ indices من 0، فلازم n + 1 خانة. بـ new Array(n) هتبقى dp[n] = undefined، و undefined + 5 = NaN من غير error. نفس غلطة FizzBuzz: "لحد n شاملة".
  3. الـ base cases: الحاجات اللي عارفينها من غير حساب.
  4. i = 2 لأن 0 و 1 اتملوا. <= لأن dp[n] هي الإجابة: بـ < هتفضل 0. و من الصغير للكبير لأن dp[i] محتاجة اللي قبلها جاهز.
  5. نفس الـ recursion، بس بنقرا من الـ array بدل ما ننادي دالة.

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

التعقيد: O(n) وقت و O(n) memory، ومفيش recursion فمفيش stack overflow.

بص على الـ animation: كل خانة محتاجة آخر اتنين بس. محتاجين الـ array كلها؟

الخطوة 3: O(1) memory

كل اللي قبل آخر خانتين عمرنا ما رجعنالهم، فمتغيرين كفاية.

  1. prev1 = dp[i - 1] و prev2 = dp[i - 2]. عند i = 2 هما 1 و 0.
  2. الترتيب هنا كل حاجة. لو بدأت بـ prev1 = cur، الـ prev2 هتاخد cur هي كمان والاتنين يبقوا نفس الرقم. اسأل: "مين محتاج القيمة القديمة؟" وحرّكه الأول.
  3. بعد آخر لفة 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. الـ statedp[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]
وحجم الـ array؟ من خطوة 1 و 5: لو الـ states من 0 لـ n شاملة، يبقى n + 1. لو الـ states indices في array طولها n، يبقى n. ما تحفظش "دايمًا n + 1"، اسأل: "أكبر index هقراه كام؟" وزوّد 1.
حيلة "آخر قرار" أصعب خطوة هي الـ transition. السؤال السحري: "آخر حاجة حصلت قبل ما أوصل للـ state دي كانت إيه؟". آخر خطوة كانت 1 ولا 2؟ آخر بيت سرقته ولا لأ؟ آخر عملة كانت أنهي واحدة؟ كل إجابة بتديك state أصغر، والـ transition بيجمعهم أو ياخد أحسنهم.

يلا نطبّق الـ recipe على أول مسألة حقيقية: Climbing Stairs.

مثال محلول 1: Climbing Stairs

Climbing Stairs

easyLeetCode 70

سلم فيه n درجة. في كل حركة بتطلع درجة أو درجتين. بكام طريقة مختلفة توصل للدرجة n؟

Input: n = 3 → 3 (1+1+1, 1+2, 2+1) Input: n = 5 → 8 Input: n = 1 → 1

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

  1. Brute force: backtracking يجرّب كل التسلسلات، وعددها exponential. مع n = 45 الإجابة 1,836,311,903، مستحيل نعدّهم واحدة واحدة.
  2. الـ state: dp[i] = عدد الطرق اللي توصّلك للدرجة i بالظبط.
  3. الـ transition (آخر قرار): آخر حركة يا درجة (كنت على i - 1) يا درجتين (كنت على i - 2)، والنوعين مختلفين تمامًا. فـ dp[i] = dp[i - 1] + dp[i - 2]. أيوه، هي fib.
  4. الـ base cases: dp[0] = 1 و dp[1] = 1. ليه dp[0] = 1 مش 0؟ "تفضل على الأرض" = طريقة واحدة: ما تعملش حاجة. ولو 0، dp[2] هتطلع 1 والصح 2 (1+1 و 2). اختبر الـ base case دايمًا بأصغر حالة بعده.
  5. الترتيب: من 2 لـ n. الإجابة: dp[n]. الحجم: n + 1.
  1. n + 1: من الأرض (0) للدرجة n. والـ constraints بتقول n >= 1، فسطر 4 آمن.
  2. الطريقة الفاضية. مش رقم "طبيعي"، بس هو اللي بيخلّي الـ transition صح عند i = 2.
  3. i <= n، لأن dp[n] هي الإجابة.
  4. بنجمع لأن المطلوب عدد طرق. لو المطلوب "أقل عدد حركات" كنا هناخد min + 1. نوع السؤال بيحدد العملية: عدد = sum، أحسن = min أو max.
Inputالمتوقعليه الحالة دي مهمة
n = 11الـ loop مش بتلف، والإجابة من الـ base case.
n = 22بتختبر dp[0] = 1.
n = 451836311903أقصى n: الـ recursion الساذجة مش هتلحق.

التعقيد: O(n) وقت، و O(n) أو O(1) memory بالمتغيرين.

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

مثال محلول 2: Min Cost Climbing Stairs

Min Cost Climbing Stairs

easyLeetCode 746

كل درجة i ليها تمن cost[i] بتدفعه لما تطلع منها (درجة أو درجتين). تبدأ من الدرجة 0 أو 1 ببلاش. السطح هو بعد آخر درجة. إيه أقل تكلفة توصّلك للسطح؟

Input: cost = [1, 100, 1, 1, 100, 1] Output: 4 (start at 0: pay 1 → 2: pay 1 → 3: pay 1 → 5: pay 1 → top) Input: cost = [5, 3] Output: 3 (start at 1, pay 3, jump to the top)

الجديد هنا إن الـ transition بياخد min بدل الجمع، وإن الإجابة مش عند آخر index: السطح هو n.

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

  1. فين السطح؟ الدرجات من 0 لـ n - 1، والسطح "الدرجة رقم n". الوقوف على آخر درجة مش معناه إنك وصلت.
  2. الـ state: dp[i] = أقل تكلفة توصّلك تقف على الدرجة i (من غير ما تدفع تمنها لسه).
  3. الـ transition: يا من i - 1 ودفعت cost[i - 1]، يا من i - 2 ودفعت cost[i - 2]، وناخد الأرخص.
  4. الـ base cases: dp[0] = dp[1] = 0، البداية ببلاش.
  5. الترتيب: من 2 لـ n. الإجابة: dp[n]. الحجم: n + 1.
  1. n + 1: الدرجات + السطح. والـ fill(0) بيعمل الـ base cases لوحده.
  2. بندفع تمن الدرجة اللي طلعنا منها. لما i = n مفيش cost[n]، وده صح: السطح ببلاش.
  3. أقل تكلفة = min. لو كتبت max الكود هيشتغل عادي ويطلّع أغلى طريق.
  4. السطح. dp[n - 1] تكلفة الوقوف على آخر درجة، ولسه ما دفعتش تمنها.

صف cost فوق و dp تحت، وفيها خانة زيادة: السطح:

التعقيد: O(n) وقت، و O(n) أو O(1) memory.

في المثالين اللي فاتوا القرار كان "جيت منين". طب لو القرار "آخد ولا أسيب"، والاختيار بيمنع اللي جنبه؟

مثال محلول 3: House Robber

House Robber

mediumLeetCode 198

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

Input: nums = [6, 2, 3, 9, 4, 1] Output: 16 (houses 0, 3, 5: 6 + 9 + 1) Input: nums = [2, 1, 1, 2] Output: 4 (houses 0 and 3)

الجديد هنا إن الـ transition = take or skip، وإن الـ state "أول i بيوت" بيدّينا حالة فاضية ببلاش.

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

  1. حلول بتبان صح وهي غلط: "الزوجي أو الفردي": 6 + 3 + 4 = 13 و 2 + 9 + 1 = 12، والصح 16 (سبنا بيتين ورا بعض). محتاجين نجرّب كل الـ choices من غير تكرار.
  2. الـ state: dp[i] = أكبر مبلغ من أول i بيوت (من 0 لـ i - 1).
  3. الـ transition (آخر قرار): البيت i - 1 يا سبناه: dp[i - 1]، يا سرقناه فجاره ممنوع: dp[i - 2] + nums[i - 1]. وناخد الأكبر.
  4. الـ base cases: dp[0] = 0 (مفيش بيوت)، dp[1] = nums[0].
  5. الترتيب: من 2 لـ n. الإجابة: dp[n]. الحجم: n + 1.
ليه "أول i بيوت" مش "لحد البيت i"؟ الاتنين صح. بس "لحد البيت i" محتاج dp[1] = max(nums[0], nums[1])، وده بيقع لو فيه بيت واحد. "أول i بيوت" بيدّيك dp[0] = 0 مجانًا. الـ trade-off: البيت بتاع dp[i] هو nums[i - 1].
  1. dp[0] = 0 من الـ fill: صفر بيوت = صفر فلوس.
  2. بيت واحد على الأقل حسب الـ constraints. لو سمحت بـ array فاضية، اكتب if (n === 0) return 0 الأول.
  3. الـ i - 1 هنا هو الـ off-by-one بتاع المسألة. بـ nums[i] هتاخد البيت اللي بعده، وفي آخر لفة nums[n] = undefined والإجابة NaN.
  4. أكبر مبلغ = 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

Coin Change

mediumLeetCode 322

عندك أنواع عملات coins، ومن كل نوع عدد مالوش آخر. إيه أقل عدد عملات يعمل المبلغ amount بالظبط؟ لو مستحيل رجّع -1.

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

الجديد هنا إن الـ transition جواه loop على كل الـ coins، وإن الـ init بقى Infinity، وإن الـ greedy اللي بيبان منطقي بيقع.

ليه الـ greedy بيقع هنا؟

"خد أكبر عملة تنفع وكرر" بتشتغل مع الفكة المصرية (200، 100، 50…) عشان متصممة كده. بس مع [1, 3, 4] و 6:

الطريقةالاختياراتعدد العملات
Greedy (الأكبر الأول)4 → فاضل 2 → 1 → فاضل 1 → 13
الصح3 + 32

الـ 4 شكلها أحسن choice دلوقتي، بس بتسيبك في 2. الـ greedy بياخد قرار ومش بيرجع فيه، فمحتاجين نجرّب كل عملة كآخر عملة.

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

  1. الـ state: dp[a] = أقل عدد عملات يعمل المبلغ a بالظبط.
  2. الـ transition (آخر عملة): لو آخر عملة c، قبلها كان معانا a - c. فـ dp[a] = min(dp[a - c] + 1) على كل c <= a.
  3. الـ base case: dp[0] = 0.
  4. الـ init: Infinity = "لسه مش عارفين نعمله". بـ 0: min(0, أي حاجة) = 0 فكله يفضل 0. بـ -1: min(-1, 3) = -1 فالـ -1 تكسب دايمًا. الـ Infinity بتخسر أي مقارنة، و Infinity + 1 لسه Infinity.
  5. الترتيب: a من 1 لـ amount. الإجابة: dp[amount] أو -1. الحجم: amount + 1.
  1. ناس بتستخدم amount + 1 بدل Infinity: مستحيل تحتاج أكتر من amount عملة. الاتنين صح، و Infinity أوضح.
  2. الـ base case الوحيد، وكل مبلغ في الآخر بيتبني عليه.
  3. c <= a عشان a - c ما يبقاش سالب. ولو dp[a - c] لسه Infinity، المقارنة عمرها ما هتبقى true، فالمبالغ المستحيلة مش بتأثر.
  4. لو نسيت التحويل هترجّع Infinity والمطلوب -1.

الـ ∞ = "لسه مش عارفين نعمله". الخانة التركوازي هي dp[a - c] اللي بنبني عليها:

Inputالمتوقعليه الحالة دي مهمة
[1], 00الـ loop مش بتلف.
[2], 3-1dp[3] بتفضل Infinity.
[1, 3, 4], 62الـ greedy بيطلّع 3.
[186, 419, 83, 408], 624920عملات كبيرة ومفيش 1: أغلب الخانات Infinity.

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

في الانترفيو ابدأ بـ: "الـ greedy مش بيشتغل هنا، مثلًا [1, 3, 4] و 6". الجملة دي لوحدها بتوري إنك فاهم ليه DP. وبعدين قول الـ state بالكلام قبل الكود.

في كل اللي فات الإجابة كانت في آخر خانة. فيه مسائل الإجابة فيها ممكن تبقى في أي خانة.

مثال محلول 5: Longest Increasing Subsequence

Longest Increasing Subsequence

mediumLeetCode 300

إيه طول أطول subsequence متزايدة بشكل صارم؟ الـ subsequence يعني تشيل عناصر من غير ما تغيّر ترتيب الباقي (مش لازم يكونوا جنب بعض).

Input: nums = [2, 6, 3, 7, 4, 1] Output: 3 (2, 6, 7 or 2, 3, 7 or 2, 3, 4) Input: nums = [7, 7, 7] Output: 1 (equal values don't count)

الجديد هنا إن الـ state "بتخلص عند i"، فالإجابة max(dp) مش آخر خانة، والحجم n مش n + 1.

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

  1. Brute force: كل subsequence = subset، يعني 2ⁿ. مع n = 2500 مستحيل.
  2. محاولة أولى: "dp[i] = أطول واحدة في أول i عناصر". المشكلة: عشان تضيف nums[i] لازم تعرف آخر عنصر في الـ sequence، والـ state ده مش بيقولك. لما الـ transition ما يتكتبش، غيّر الـ state.
  3. الـ state الصح: dp[i] = طول أطول increasing subsequence بتخلص عند nums[i]. كده آخر عنصر معروف.
  4. الـ transition: قبل nums[i] كان فيه nums[j] أصغر منه (j < i)، أو مفيش. فـ dp[i] = 1 + max(dp[j])، ولو مفيش j يبقى 1.
  5. Base: كله 1. الحجم: n، لأن الـ states indices من 0 لـ n - 1. الإجابة: max على كل الـ dp، لأن الـ LIS ممكن تخلص عند أي عنصر.
  1. الـ 1 دي الـ base case و "مفيش j" في نفس الوقت.
  2. best = 1 مش 0، عشان لو n = 1 الإجابة 1.
  3. i < n مش <=، لأن الـ states هنا indices لحد n - 1. قارن بـ Climbing Stairs: هناك الـ states لحد n. الفرق جاي من خطوة 1.
  4. < مش <=، عشان strictly increasing. بـ <=، [7, 7, 7] هتطلع 3.
  5. بديل إنك تعمل Math.max(...dp) في الآخر.

i بيلف، و j بيعدّي على اللي قبله. الأخضر = ينفع نمد منه، والأحمر = لأ:

التعقيد: O(n²) وقت و O(n) memory. مع n = 2500 ده حوالي 3 مليون عملية، يعدّي.

فكرة الـ O(n log n) (للمعلومة)

احتفظ بـ tails: tails[k] = أصغر عنصر ممكن تخلص بيه increasing subsequence طولها k + 1. الـ array دي دايمًا مترتبة، فلكل عنصر تعمل binary search على أول خانة أكبر منه أو بتساويه وتحطه مكانها (أو في الآخر). طول tails هو الإجابة، بس tails نفسها مش الـ LIS.

قارنته بنسخة الـ O(n²) على 300 array عشوائية، ونفس الإجابات.

آخر مثال: dp من true/false، والسؤال فيه "أقطع فين".

مثال محلول 6: Word Break

Word Break

mediumLeetCode 139

عندك string s وقاموس كلمات. هل تقدر تقطّع s لكلمات كلها من القاموس؟ (نفس الكلمة مسموح تتكرر.)

Input: s = "sunflower", wordDict = ["sun", "flow", "er", "flower"] Output: true ("sun" + "flower", or "sun" + "flow" + "er") Input: s = "sunflowers", same dict Output: false (nothing covers the last "s")

الجديد هنا إن الـ dp بـ true/false، والـ transition بيدوّر على مكان القطع j.

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

  1. Brute force: backtracking يجرّب كل كلمة في البداية ويكمّل. مع "aaaa…ab" و ["a", "aa", "aaa"] بينفجر، و "هل الباقي من index 5 بيتقطّع؟" بيتسأل مرات كتير: overlapping subproblems.
  2. الـ state: dp[i] = هل أول i حروف (s.slice(0, i)) بيتقطّعوا؟
  3. الـ transition (آخر كلمة): آخر كلمة بتبدأ عند j وبتخلص عند i. الشرط: dp[j] true، و s.slice(j, i) في القاموس.
  4. الـ base case: dp[0] = true: الـ string الفاضي = صفر كلمات. من غيره مفيش أي true، لأن أول كلمة بتبدأ عند 0.
  5. الترتيب: i من 1 لـ n. الإجابة: dp[n]. الحجم: n + 1.
  1. Set بدل includes اللي بتلف على القاموس كله كل مرة.
  2. الـ base case اللي كل true بتتبني عليه.
  3. j = بداية آخر كلمة. j = 0 يعني الـ prefix كله كلمة واحدة.
  4. s.slice(j, i) من j لحد i - 1، والـ i مش داخل، وده بالظبط الـ prefix بتاع dp[i]. و dp[j] الأول: لو false، الـ && بتقف قبل الـ slice.
  5. طريقة واحدة كفاية. الـ 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 II

mediumLeetCode 213

نفس House Robber، بس البيوت في دايرة: أول بيت وآخر بيت جيران.

[2, 3, 2] → 3 [1, 2, 3, 1] → 4 [4, 1, 2, 7, 5, 3, 1] → 14 (houses 0, 3, 5: 4 + 7 + 3)
تلميح 1

المشكلة كلها في أول وآخر بيت: مينفعش ياخدوا الاتنين. يعني يا أول بيت مش مسروق، يا آخر بيت مش مسروق.

تلميح 2

شيل أول بيت: الدايرة تبقى خط. شيل آخر بيت: برضه خط. احسب House Robber العادي على الاتنين وخد الأكبر. وخلي بالك من بيت واحد بس.

الحل

مع بيت واحد الـ slice الاتنين فاضيين والإجابة تطلع 0، عشان كده الـ if. جرّبته على الأمثلة التلاتة وعلى [7] (طلعت 7).

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

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

في كل مسألة اكتب الخمس خطوات كـ comments قبل الكود. ولو اتزنقت: recursion ساذجة، وبعدين memo، وبعدين table.

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

الخلاصة

في جملة واحدة DP = recursion بتفتكر: عرّف الـ state بالكلام، واكتب الإجابة من states أصغر عن طريق آخر قرار، واحسب كل state مرة واحدة بالترتيب الصح.
المسألةالـ stateالـ transitionbaseالإجابة
Climbing Stairsطرق الوصول لدرجة idp[i-1] + dp[i-2]dp[0]=dp[1]=1dp[n]
Min Cost Stairsأقل تكلفة للوقوف على imin(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])dp[0]=dp[1]=0dp[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أقل عملات للمبلغ amin over c of dp[a-c]+1dp[0]=0, rest ∞dp[amount] or -1
LISأطول increasing بتخلص عند i1 + max dp[j], j<i, nums[j]<nums[i]all 1max(dp)
Word Breakأول i حروف بيتقطّعوا؟any j: dp[j] and s[j..i) in dictdp[0]=truedp[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 هيتنقلوا هناك زي ما هم، بس في بعدين.