House Robber

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.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

إما أن تتجاوز أي خطة المنزل الأخير أو تأخذه. يؤدي التجاوز إلى اختيار أفضل خطة للمنازل n-1 الأولى؛ أما أخذه فيضيف nums[n-1] إلى أفضل خطة للمنازل n-2 الأولى. إذن 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 مليون استدعاء، بينما يصل n إلى 10^4.

الخوارزمية

اكتب دالة مساعدة 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، بدءًا من best[0] = 0 وbest[1] = nums[0]، واملأ الجدول تصاعديًا بدءًا من k = 2، بحيث تكون القيمتان اللتان تقرؤهما كل إجابة موجودتين بالفعل.

بالنسبة إلى [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]

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

الفكرة

يقرأ كل إدخال الإدخالين السابقين له فقط، لذا احتفظ برقمين بدلًا من الجدول: twoBack وoneBack، وهما أفضل مجموع حتى منزلين سابقين وحتى المنزل السابق. إذا كان المنزل يحتوي على x، فإن أفضل مجموع جديد هو max(oneBack, twoBack + x)؛ ثم حرّك القيمتين إلى الأمام. تبدأ القيمتان عند 0، وهو الشارع الخالي قبل المنزل الأول، لذا لا يحتاج الشارع الذي يحتوي على منزل واحد إلى حالة خاصة. يظل الزمن 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

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

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

أسئلة شائعة3

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

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

لماذا لا يؤدي أخذ منزل وترك المنزل التالي بالتناوب إلى حل مسألة سرقة المنازل؟

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

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

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

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

اختبار #1

اختبار #2

اختبار #3

وسيط

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

الإخراج المتوقع

House Robber

الدالة

القيود

أمثلة

تلميحات

الحل

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

جدول من الأسفل إلى الأعلى

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

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

أسئلة شائعة3

مسائل مشابهة