Tous les défis
Moyen 1 résolu 100.0 % de réussite

Compter les combinaisons de pièces

Comptez le nombre de façons de former un montant avec un nombre illimité de pièces de valeurs spécifiées.

Ce que vous allez apprendre

  • Compter les combinaisons, pas les ordres
  • Parcourir les pièces dans la boucle externe
  • Construire un tableau de DP 1D des façons

Problème

Utilisez autant de chaque valeur fournie que nécessaire pour former exactement le montant. Comptez les combinaisons, pas les arrangements : deux façons utilisant le même nombre de chaque pièce comptent comme une seule combinaison. Les valeurs sont distinctes et strictement positives.

Implémentez coin_sums(amount, coins).

Entrée

amount : Le montant total à former.

coins : Les valeurs distinctes disponibles.

Sortie

Retournez le nombre de combinaisons sans ordre.

Contraintes

0 ≤ amount ≤ 200. Il y a de 0 à 10 valeurs distinctes, chacune comprise entre 1 et 200. Tous les résultats tiennent dans un entier signé 64 bits. Pour amount = 0, il existe une seule façon : ne choisir aucune pièce.

Exemples

Exemple 1
Entrée :
amount = 4
coins = [1, 2]

Sortie attendue :
expected = 3
Entrée :
long long amount = 4;
std::vector<long long> coins = {1, 2};

Sortie attendue :
long long expected = 3;
Entrée :
long amount = 4;
long[] coins = new long[] {1, 2};

Sortie attendue :
long expected = 3;

Explication

Les combinaisons sont : quatre pièces de 1, deux pièces de 1 avec une pièce de 2, et deux pièces de 2.

Exemple 2
Entrée :
amount = 3
coins = [2]

Sortie attendue :
expected = 0
Entrée :
long long amount = 3;
std::vector<long long> coins = {2};

Sortie attendue :
long long expected = 0;
Entrée :
long amount = 3;
long[] coins = new long[] {2};

Sortie attendue :
long expected = 0;

Explication

Toute somme de pièces de valeur 2 est paire, donc 3 est impossible.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

L’ordre des pièces ne compte pas, donc il faut compter les combinaisons par dénomination, pas les permutations.

Indice 2

Construis le nombre de façons pour chaque montant progressivement, en laissant chaque pièce contribuer à tous les totaux atteignables.

Indice 3

Attention au montant zéro, qui a toujours une seule façon valide : ne prendre aucune pièce.

Complexité attendue

temps O(amount × number_of_coins), espace supplémentaire O(amount)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 811 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.