Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Münzkombinationen zählen

Zähle die Möglichkeiten, einen Betrag mit unbegrenzt vielen Münzen gegebener Stückelungen zu bilden.

Das lernst du

  • Kombinationen statt Reihenfolgen zählen
  • Die Münzen in der äußeren Schleife durchlaufen
  • Ein 1D-DP-Array der Möglichkeiten aufbauen

Problem

Verwende beliebig viele Münzen jeder angegebenen Stückelung, um den Betrag exakt zu erreichen. Es sollen Kombinationen gezählt werden, nicht Anordnungen: Zwei Zusammenstellungen mit denselben Anzahlen jeder Münze gelten als dieselbe Möglichkeit. Die Stückelungen sind verschieden und positiv.

Implementiere coin_sums(amount, coins).

Eingabe

amount: Der zu bildende Gesamtbetrag.

coins: Die verfügbaren, verschiedenen Stückelungen.

Ausgabe

Gib die Anzahl der ungeordneten Kombinationen zurück.

Einschränkungen

0 ≤ amount ≤ 200. Es gibt 0 bis 10 verschiedene Stückelungen, jede im Bereich von 1 bis 200. Alle Anzahlen passen in ein vorzeichenbehaftetes 64-Bit-Integer. Für amount 0 gibt es genau eine Möglichkeit: keine Münzen wählen.

Beispiele

Beispiel 1
Eingabe:
amount = 4
coins = [1, 2]

Erwartete Ausgabe:
expected = 3
Eingabe:
long long amount = 4;
std::vector<long long> coins = {1, 2};

Erwartete Ausgabe:
long long expected = 3;
Eingabe:
long amount = 4;
long[] coins = new long[] {1, 2};

Erwartete Ausgabe:
long expected = 3;

Erläuterung

Die Kombinationen sind vier 1er, zwei 1er mit einer 2er, und zwei 2er.

Beispiel 2
Eingabe:
amount = 3
coins = [2]

Erwartete Ausgabe:
expected = 0
Eingabe:
long long amount = 3;
std::vector<long long> coins = {2};

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long amount = 3;
long[] coins = new long[] {2};

Erwartete Ausgabe:
long expected = 0;

Erläuterung

Jede Summe aus 2er-Münzen ist gerade, daher ist 3 nicht möglich.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Die Reihenfolge der Münzen spielt keine Rolle, also sollten Kombinationen nach Nennwert und nicht nach Permutation gezählt werden.

Hinweis 2

Baue die Anzahl der Wege für jeden Betrag schrittweise auf, sodass jede Münze zu allen erreichbaren Summen beitragen kann.

Hinweis 3

Achte auf den Betrag 0, der immer genau einen gültigen Weg hat: keine Münzen wählen.

Erwartete Komplexität

Zeit O(amount × number_of_coins), zusätzlicher Speicher O(amount)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 811 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.