Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Count Coin Combinations

Count ways to make an amount with unlimited coins of specified denominations.

Das lernst du

  • Count combinations, not orderings
  • Loop over coins in the outer loop
  • Build a 1D DP array of ways

Problem

Übersetzung anzeigen

Use any number of each supplied denomination to make amount exactly. Count combinations, not orderings: two arrangements using the same counts of each coin are the same way. Denominations are distinct and positive.

Implement coin_sums(amount, coins).

Input

amount: The total amount to make.

coins: The available distinct denominations.

Output

Return the number of unordered combinations.

Einschränkungen

0 ≤ amount ≤ 200. There are 0 through 10 distinct denominations, each from 1 through 200. All counts fit signed 64-bit. Amount 0 has one way: choose no coins.

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

The combinations are four 1s, two 1s with one 2, and two 2s.

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

Any sum of 2-valued coins is even, so 3 is impossible.

So gehst du vor

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

Hinweis 1

The order of coins does not matter, so combinations should be counted by denomination, not by permutation.

Hinweis 2

Build the number of ways for each amount incrementally, letting each coin contribute to all reachable totals.

Hinweis 3

Be careful with amount zero, which always has one valid way: choose no coins.

Erwartete Komplexität

O(amount × number_of_coins) time, O(amount) extra space

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.