Coin Change
لديك قائمة coins تضم قيمًا مختلفة للعملات ومبلغًا مستهدفًا amount. يمكنك استخدام كل قيمة من قيم العملات أي عدد من المرات. أعد أقل عدد من العملات التي تجمع قيمها إلى amount بالضبط، أو -1 إذا لم تصل أي مجموعة من العملات إلى هذا المبلغ. المبلغ 0 لا يحتاج إلى أي عملات.
الدالة
- coinsinteger-array
- قيم العملات المختلفة، ويمكن استخدام كلٍّ منها أي عدد من المرات
- amountinteger
- إجمالي المبلغ المطلوب دفعه بالضبط
- تُرجعinteger
- أقل عدد من العملات اللازمة، أو -1 إذا تعذّر تكوين المبلغ
القيود
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- جميع قيم العملات مختلفة.
أمثلة
- المدخلات
- coins = [2, 5, 10]amount = 27
- المخرجات
- 4
- الشرح
- 10 + 10 + 5 + 2 تساوي 27 باستخدام أربع عملات. ثلاث عملات لا تكفي: 27 عدد فردي، لذا يحتاجون إلى 5 واحدة بالضبط، والاثنتان الأخريان مجموعهما 20 كحد أقصى، وهو أقل من 22.
- المدخلات
- coins = [4, 6]amount = 7
- المخرجات
- -1
- الشرح
- قيمة كلتا العملتين زوجية، لذا فإن كل مجموع يمكنك تكوينه سيكون زوجيًا. العدد 7 فردي، لذا فالإجابة هي -1.
- المدخلات
- coins = [3, 7]amount = 0
- المخرجات
- 0
- الشرح
- دفع 0 لا يتطلب أي عملات على الإطلاق، لذا فالإجابة هي 0 مهما كانت قيم العملات.
سؤال إضافي
هل يمكنك حساب عدد التوليفات المختلفة من العملات التي يساوي مجموعها amount، بدلًا من إيجاد أقل عدد من العملات؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إن اختيار أكبر عملة تناسب المبلغ في كل مرة لا يعطي دائمًا أقل عدد من العملات. جرّب ذلك على العملات
[1, 3, 4]والمبلغ6.افترض أنك تعرف بالفعل أقل عدد من العملات لكل مبلغ أصغر من
t. ما المبالغ الأصغر التي يمكن الوصول منها إلىtبإضافة عملة واحدة؟املأ جدول
fewest[0..amount]بدءًا من0صعودًا:fewest[0] = 0، وكل قيمةfewest[t]تساوي أفضل قيمةfewest[t - c]بين العملاتc <= tزائد واحد. علّم المبالغ التي لا يمكن الوصول إليها بقيمة أكبر من أي إجابة حقيقية، مثلamount + 1، وحوّلها إلى-1في النهاية.
الحل
اختيار أكبر عملة تناسب المبلغ لا ينجح دائمًا: باستخدام العملات 1 و3 و4، يُدفع المبلغ 6 على شكل 4 + 1 + 1، بينما يحتاج 3 + 3 إلى عملتين. يعتمد أقل عدد من العملات لمبلغٍ ما فقط على أقل عدد من العملات للمبالغ الأصغر، لذا تحسب كل مبلغ من 0 إلى amount مرة واحدة.
جرّب كل التركيبات باستخدام الاستدعاء الذاتي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
إذا كانت قيمة آخر عملة تدفعها هي c، فإن العملات التي تسبقها تدفع remaining - c بأقل تكلفة ممكنة. لذا فإن fewest(remaining) تساوي واحدًا زائد أفضل قيمة لـ fewest(remaining - c) بين جميع العملات التي لا تتجاوز المبلغ المتبقي. يجرّب هذا كل تسلسلات العملات التي لا تتجاوز المبلغ، لذا لا يمكنه تفويت أفضل تسلسل.
ويحلّ المبالغ نفسها مرارًا وتكرارًا. باستخدام العملات 2 و5 و10، يصل المبلغ 27 إلى 15 بعد دفع 10 + 2، أو 2 + 10، أو 5 + 5 + 2، وبترتيبات أخرى كثيرة، ويحسب قيمة 15 من البداية في كل مرة. يزداد عدد الاستدعاءات أُسّيًا مع المبلغ.
الخوارزمية
- اكتب دالة مساعدة
fewest(remaining)تُرجع أقل عدد من العملات لـremaining، أو -1 إذا لم تنجح أي منها. - إذا كانت
remainingتساوي 0، فأرجع 0. - لكل عملة لا تتجاوز قيمتها
remaining، استدعِ الدالة المساعدة مع المبلغ المتبقي بعد دفع تلك العملة. - احتفظ بأصغر نتيجة لا تساوي -1، وأضف إليها واحدًا مقابل العملة التي دفعتها.
- أرجع هذا العدد، أو -1 إذا لم تؤدِّ أي عملة إلى نتيجة. الإجابة هي
fewest(amount).
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)الاستدعاء الذاتي مع التخزين المؤقت
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يسأل الاستدعاء الذاتي فقط عن المبالغ من 0 إلى amount. خزّن كل إجابة في مصفوفة عند حسابها لأول مرة، وأعِد القيمة المخزّنة عندما يظهر ذلك المبلغ مجددًا. يُحل كل مبلغ مرة واحدة باستخدام حلقة تمر على العملات: عمل بمقدار O(amount × coins).
تظل الاستدعاءات متداخلة بمستوى واحد لكل عملة تُدفع. ومع عملة قيمتها 1، قد يصل ذلك إلى 10^4 مستوى، وهو أكثر مما يسمح به مكدس الاستدعاءات الافتراضي في كثير من اللغات.
الخوارزمية
- أنشئ مصفوفة
memoتتسع لكل المبالغ من 0 إلىamount، وتحتوي على علامة تعني أن الحساب لم يُجرَ بعد. - في
fewest(remaining)، أرجِع 0 إذا كانت القيمة 0، وأرجِعmemo[remaining]إذا كانت تحتوي بالفعل على إجابة. - وإلا، فجرّب كل عملة تناسب المبلغ، كما في الاستدعاء الذاتي البسيط، واحتفظ بأصغر نتيجة زائد واحد.
- احفظ النتيجة، بما في ذلك -1، في
memo[remaining]قبل إرجاعها. - أرجِع
fewest(amount).
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)البرمجة الديناميكية التصاعدية على المبالغ
الفكرة
املأ جدول fewest بدءًا من 0 تصاعديًا. عندما تصل إلى إجمالي t، يكون كل إجمالي أصغر قد حُسم، لذا تكون قيمة fewest[t] أكبر بواحد من أصغر قيمة fewest[t-c] بين العملات c التي تناسب.
تحمل الإجماليات التي لا يمكن الوصول إليها بأي مزيج من العملات العلامة amount + 1. قيمة كل عملة لا تقل عن 1، لذا لا تستخدم الإجابة الحقيقية أكثر من amount عملة، وتخسر العلامة في كل مقارنة. تحل حلقة محل الاستدعاء التكراري، لذا لا يؤثر عمق مكدس الاستدعاءات مطلقًا.
الخوارزمية
- أنشئ
fewestمعamount + 1من العناصر، واجعل قيمة كل منها العلامةamount + 1، ثم عيّنfewest[0]إلى 0. - لكل إجمالي
tمن 1 إلىamount، افحص كل عملةcبحيثc ≤ t. - إذا كانت
fewest[t-c] + 1أصغر منfewest[t]، فخزّنها فيfewest[t]. - بعد الحلقة، أعد -1 إذا كانت
fewest[amount]لا تزال تحمل العلامة، وأعدfewest[amount]خلاف ذلك.
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
أخطاء شائعة وحالات حدّية
- أخذ أكبر عملة أولًا. باستخدام العملتين 3 و5 والمبلغ 9، يدفع 5 و3، ثم يتعثر عند 1 ويُرجع -1، بينما يعمل الحل 3 + 3 + 3.
- استخدام أكبر عدد صحيح كعلامة. تؤدي إضافة 1 إليه إلى تجاوز سعته وتحويله إلى عدد سالب، فيفوز بعد ذلك في كل مقارنة. استخدم
amount + 1. - إضافة 1 إلى طريق مسدود. الفرع الذي يُرجع -1، مضافًا إليه قيمة العملة التي دفعتها، يعطي 0 ويفوز في كل مقارنة. تخطَّ النتائج -1.
- الاستدعاء التكراري بعمق
amountمستوى. باستخدام عملة قيمتها 1 ومبلغ10^4، يتوقف Python عند حدّه الافتراضي البالغ 1000 مستوى، وينفد مكدس الاستدعاءات أيضًا في JavaScript وDart وRuby وR. - قراءة
fewest[t-c]لعملة أكبر منt، أي قبل بداية الجدول.
أسئلة شائعة3
لماذا يفشل النهج الجشع في مسألة تبديل العملات؟
إن اختيار أكبر قطعة نقدية تناسب المبلغ يكون آمنًا فقط في بعض أنظمة العملات، مثل معظم العملات الحقيقية. باستخدام قطع نقدية بقيم 1 و3 و4، يمكن دفع 6 بثلاث قطع بدلًا من قطعتين، وباستخدام قطع نقدية بقيم 3 و5، لا يمكن دفع 9 على الإطلاق. تقارن البرمجة الديناميكية كل الخيارات، لذلك لا يمكن خداعها بأي نظام عملات.
ما هو التعقيد الزمني لمسألة تغيير العملات؟
يستغرق حل البرمجة الديناميكية وقتًا قدره O(amount × coins) ومساحة قدرها O(amount): مدخل واحد في الجدول لكل مبلغ، مع التحقق من كل عملة لكل مدخل. أما الاستدعاء الذاتي العادي دون تخزين مؤقت، فيكون أُسّيًا بالنسبة إلى المبلغ.
هل النهج من أعلى إلى أسفل أم من أسفل إلى أعلى أفضل لمشكلة تغيير العملات؟
كلاهما ينفذ العمل نفسه O(amount × coins). قد يصل عمق الاستدعاء التكراري من الأعلى إلى الأسفل إلى مقدار المبلغ، مما يؤدي إلى تجاوز سعة مكدس الاستدعاءات عند 10^4 في عدة لغات. أما الأسلوب من الأسفل إلى الأعلى فيملأ الجدول باستخدام حلقة، لذا لا يفرض حدًا على العمق، وهو الخيار الأكثر أمانًا في مقابلة العمل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def coinChange(coins, amount):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
coins = [2, 5, 10] amount = 27
الإخراج المتوقع
4