House Robber

Q: ما هي علاقة التكرار لمسألة «لصّ المنازل»؟

أفضل مجموع من المنازل الأولى وعددها k هو max(best[k-1], best[k-2] + nums[k-1]) . إما أن تتخطى المنزل k-1 وتحتفظ بأفضل مجموع من المنازل التي تسبقه، أو تأخذ المنزل k-1 وتضيفه إلى أفضل مجموع ينتهي قبل المنزل المجاور له. الحالتان الأساسيتان هما 0 عند عدم وجود منازل، و nums[0] عند وجود منزل واحد.

Q: لماذا لا يحل أخذ منزل وترك المنزل الذي يليه دائمًا مسألة «سارق المنازل»؟

أفضل خطة تتجاوز أحيانًا منزلين متتاليين. في [10, 1, 1, 10] ، يكون مجموع المنازل ذات الفهارس الزوجية ومجموع المنازل ذات الفهارس الفردية 11 لكل منهما، بينما يعطي أخذ المنزل الأول والأخير 20. تقارن البرمجة الديناميكية بين التجاوز والأخذ عند كل منزل، لذا تجد تلك الخطط.

متوسطالبرمجة الديناميكية

+10

تقف المنازل في صف على امتداد شارع، وتمثّل nums[i] الأموال الموجودة في المنزل i. يمكنك أخذ المال من أي منازل تختارها، لكن لا تأخذه أبدًا من منزلين متجاورين. أعد أكبر مجموع يمكنك أخذه.

الدالة

rob(nums: integer-array) → integer

numsinteger-array: الأموال في كل منزل، حسب ترتيب الشارع
تُرجعinteger: أكبر مجموع يمكنك الحصول عليه دون الأخذ من منزلين متجاورين

القيود

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
الإجابة لا تتجاوز 5 × 10⁶، لذا فهي تتسع في عدد صحيح موقّع من 32 بت.

أمثلة

المدخلات: nums = [5, 3, 4, 11, 2]
المخرجات: 16
الشرح: خذ 5 و11 من المنزلين 0 و3 لتحصل على 16. يُسمح بتجاوز منزلين متتاليين، وهنا يتفوق ذلك على كل الخطط الأخرى: 5 + 4 + 2 = 11 و3 + 11 = 14.

+16 اختبارات مخفية عند الإرسال

سؤال إضافي

أعِد المنازل المطلوب أخذها بالإضافة إلى الإجمالي. ما الذي عليك الاحتفاظ به من الجدول لإعادة إنشاء هذه القائمة، وهل لا يزال بإمكان الإجماليين الجاريين القيام بذلك؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

الاختصارات الواضحة لا تنجح. فتجاوز كل منزل وأخذ المنزل الذي يليه يفوّت خططًا تتجاوز منزلين متتاليين، مثل 5 و11 في [5, 3, 4, 11, 2]، كما أن أخذ المنزل الأغنى أولًا يفشل مع [3, 4, 3]، حيث يمنع المنزل ذو القيمة 4 أخذ منزلين تبلغ قيمتهما معًا 6. ما ينجح هو اتخاذ القرار بشأن منزل واحد في كل مرة: يعتمد أفضل مجموع حتى منزل معين فقط على أفضل المجاميع حتى المنزلين السابقين له.

جرّب كلا الخيارين عند كل منزل

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

انظر إلى المنزل الأخير، المنزل n-1. كل خطة إما أن تتجاوزه أو تأخذه. إذا تجاوزته، فأفضل ما يمكن تحقيقه هو أفضل خطة للمنازل n-1 الأولى. وإذا أخذته، يصبح المنزل n-2 محظورًا، لذا نضيف nums[n-1] إلى أفضل خطة للمنازل n-2 الأولى. والإجابة هي الأكبر من الخيارين.

اكتب ذلك على هيئة دالة most(k)، أي أكبر قيمة يمكنك أخذها من المنازل k الأولى: most(k) = max(most(k-1), most(k-2) + nums[k-1])، مع most(0) = 0 عند عدم وجود منازل، وmost(1) = nums[0] عند وجود منزل واحد. كل خطة تتجاوز منزلها الأخير أو تأخذه، لذا يغطي الفرعان جميع الخطط وتكون النتيجة صحيحة.

هذا بطيء لأن الفرعين يتداخلان. تستدعي most(k-1) الدالة most(k-2) مرة أخرى، فتُجاب عن السؤال نفسه مرارًا وتكرارًا، وينمو عدد الاستدعاءات مثل أعداد فيبوناتشي، أي نحو 1.6^n. يتطلب التعامل مع أربعين منزلًا بالفعل أكثر من 300 مليون استدعاء، بينما تحتوي الاختبارات على ما يصل إلى 10^4 منزل. كما تتداخل الاستدعاءات بعمق يصل إلى n مستوى، متجاوزة الحد الافتراضي في Python البالغ 1000.

الخوارزمية

اكتب دالة مساعدة most(k) تُعيد أكبر مبلغ يمكنك أخذه من المنازل k الأولى.
أعِد 0 عندما تكون k تساوي 0، وnums[0] عندما تكون k تساوي 1.
وإلا، احسب skip = most(k-1) وtake = most(k-2) + nums[k-1].
أعِد الأكبر من القيمتين. الإجابة هي most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

جدول تصاعدي

الفكرة

لا يسأل الاستدعاء الذاتي إلا عن most(0) حتى most(n)، لذا توجد n + 1 أسئلة مختلفة. أجب عن كل سؤال مرة واحدة، وخزّن الإجابة في جدول، واملأ الجدول بترتيب تكون فيه كل إجابة تقرؤها موجودة مسبقًا. تحدد أربعة قرارات هذا الجدول.

الحالة: best[k] هو أكبر مجموع يمكنك أخذه من أول k منازل. علاقة التكرار: best[k] = max(best[k-1], best[k-2] + nums[k-1]): تخطَّ المنزل k-1، أو خذه بالإضافة إلى أفضل مجموع ينتهي قبل المنزل المجاور له. الحالات الأساسية: best[0] = 0 وbest[1] = nums[0]. الترتيب: تتراوح قيمة k من 2 حتى n، لأن كل خانة تقرأ الخانتين السابقتين لها.

بالنسبة إلى [5, 3, 4, 11, 2]، يكون الجدول 0, 5, 5, 9, 16, 16. عند k = 4، تقارن بين تخطي المنزل 3، وقيمته best[3] = 9، وأخذ قيمته 11 بالإضافة إلى best[2] = 5؛ فيكون المجموع 16 هو الأكبر. الإجابة هي الخانة الأخيرة. تتطلب كل خانة مقارنة واحدة، لذا الزمن هو O(n)، ويحتاج الجدول إلى مساحة O(n).

الخوارزمية

أنشئ جدولًا باسم best يحتوي على n + 1 مدخلًا.
عيّن best[0] = 0 وbest[1] = nums[0].
لكل k من 2 إلى n، عيّن best[k] إلى الأكبر بين best[k-1] وbest[k-2] + nums[k-1].
أعِد best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

مجموعان تراكميان

الفكرة

يقرأ كل مدخل في الجدول المدخلين اللذين يسبقانه مباشرةً فقط. بعد معرفة best[k]، لا يُقرأ best[k-2] مرة أخرى. لذا احتفظ برقمين بدلًا من الجدول: twoBack، وهو أفضل مجموع من المنازل حتى منزلين إلى الخلف، وoneBack، وهو أفضل مجموع حتى المنزل السابق.

لمنزل يحتوي على x، يكون الأفضل الجديد هو max(oneBack, twoBack + x). ثم حدّث القيم: تأخذ twoBack قيمة oneBack القديمة، وتأخذ oneBack قيمة الأفضل الجديد. تبدأ القيمتان عند 0، وهو ما يمثّل الشارع الخالي قبل المنزل الأول، لذا لا يحتاج المنزل الأول إلى حالة خاصة: أفضل مجموع له هو max(0, 0 + nums[0]).

على [5, 3, 4, 11, 2] يصبح الزوج (0, 0)، (0, 5)، (5, 5)، (5, 9)، (9, 16)، (16, 16)، وتنتهي قيمة oneBack عند 16. يظل العمل O(n)، مثل الجدول، بينما تنخفض الذاكرة إلى O(1).

الخوارزمية

اضبط twoBack وoneBack على 0.
لكل قيمة x في nums، احسب current = max(oneBack, twoBack + x).
انقل oneBack إلى twoBack، ثم انقل current إلى oneBack.
بعد المنزل الأخير، أعد oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

أخطاء شائعة وحالات حدّية

تنتج معظم الإجابات الخاطئة عن اختصار ينجح مع المدخلات الصغيرة، أو عن تحديث المجموعين بالترتيب الخاطئ.

جمع مبالغ المنازل الزوجية ومبالغ المنازل الفردية واختيار الأكبر يفوّت الخطط التي تتخطى منزلين متتاليين. في [10, 1, 1, 10]، كلا المجموعين يساوي 11، لكن اختيار المنزلين 0 و3 يعطي 20.
اختيار المنزل الأغنى أولًا لا ينجح مع [3, 4, 3]: إذ يختار 4 ويمنع اختيار المنزلين اللذين يحتوي كل منهما على 3، مع أن مجموعهما 6.
استبدال oneBack قبل نسخه إلى twoBack يفقد القيمة التي يحتاج إليها المنزل التالي. احسب أفضل قيمة جديدة أولًا، ثم حرّك القيم، أو عيّن القيمتين معًا عندما تسمح اللغة بذلك.
قراءة nums[1] أو تعيين best[1] وbest[2] في البداية يسبب مشكلة في شارع فيه منزل واحد. بدء المجموعين بالقيمة 0 يلغي هذه الحالة الخاصة.
في Lua وR، تبدأ المصفوفات من 1، لذا فإن المال في المنزل k-1 هو nums[k].

أسئلة شائعة4

ما هي علاقة التكرار لمسألة «لصّ المنازل»؟

أفضل مجموع من المنازل الأولى وعددها k هو max(best[k-1], best[k-2] + nums[k-1]). إما أن تتخطى المنزل k-1 وتحتفظ بأفضل مجموع من المنازل التي تسبقه، أو تأخذ المنزل k-1 وتضيفه إلى أفضل مجموع ينتهي قبل المنزل المجاور له. الحالتان الأساسيتان هما 0 عند عدم وجود منازل، وnums[0] عند وجود منزل واحد.

ما هو التعقيد الزمني وتعقيد المساحة لمسألة لصّ المنازل؟

يفحص حل البرمجة الديناميكية كل منزل مرة واحدة، لذا يستغرق وقتًا قدره O(n). يستخدم الجدول الكامل مساحة قدرها O(n)، ويؤدي الاحتفاظ بالمجموعين الأخيرين فقط إلى تقليلها إلى O(1). أما الاستدعاء التكراري العادي دون تخزين الإجابات، فيُجري نحو 1.6^n استدعاءً، وهذا نمو أُسّي.

لماذا لا يحل أخذ منزل وترك المنزل الذي يليه دائمًا مسألة «سارق المنازل»؟

أفضل خطة تتجاوز أحيانًا منزلين متتاليين. في [10, 1, 1, 10]، يكون مجموع المنازل ذات الفهارس الزوجية ومجموع المنازل ذات الفهارس الفردية 11 لكل منهما، بينما يعطي أخذ المنزل الأول والأخير 20. تقارن البرمجة الديناميكية بين التجاوز والأخذ عند كل منزل، لذا تجد تلك الخطط.

كيف تحل مسألة سرقة المنازل عندما تكون المنازل مرتبة على شكل دائرة؟

في الدائرة، يكون المنزل الأول والأخير متجاورين، لذا يمكن أن تتضمن الخطة أحدهما على الأكثر. نفّذ حل الشارع المستقيم مرتين: مرةً من دون المنزل الأخير ومرةً من دون المنزل الأول، ثم أعد النتيجة الأكبر. الشارع الذي يحتوي على منزل واحد هو الحالة الخاصة الوحيدة: والإجابة هي ذلك المنزل.

Python

def rob(nums):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [5, 3, 4, 11, 2]

المتوقع

House Robber

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب كلا الخيارين عند كل منزل

جدول تصاعدي

مجموعان تراكميان

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة