Combination Sum

Étant donné une valeur cible N et un tableau de nombres positifs autorisés, vous devez déterminer le nombre de façons d’écrire N comme somme de ces nombres.

Ainsi, si les valeurs autorisées sont par exemple [1, 2, 3], et que le nombre N vaut 4, on peut calculer ce total de 7 manières différentes :

Toutes les 7 façons de combiner 1, 2, 3 pour obtenir 4

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

C’est un problème classique de programmation dynamique. L’idée consiste à maintenir un tableau d’états d[sum] indiquant le nombre de façons de constituer sum grâce aux nombres autorisés :

N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = toutes les combinaisons qui permettent d'obtenir i
d[0] = 1                   # Il existe 1 façon d'obtenir 0 : ne rien choisir

for i in range(1, N + 1):  # On essaie d'obtenir toutes les valeurs de 1 à N
    for num in nums:       # On contribue à d[i] à l'aide de num
        if i - num >= 0:   # Si on peut former i à partir de num
            d[i] += d[i - num]
print(d[N])

Ainsi, d[i] représente le nombre de façons de constituer la valeur i en utilisant les nombres autorisés nums. Au départ, nous mettons toutes les valeurs de d à 0, sauf d[0] qui est à 1 (puisqu’il n’y a qu’une seule façon d’obtenir 0 : ne sélectionner aucun nombre). Pour chaque nombre i, on parcourt les différents nombres de nums afin de combiner les possibilités.

Par exemple, si d[11] vaut déjà 5, et que d[8] vaut 3, dès lors qu’il existe 3 dans nums, on peut former 11 en reprenant toutes les combinaisons actuelles pour 11 et en y ajoutant toutes celles pour 8, auxquelles on ajoute ce 3.

Faisons une simulation sur l’exemple :

nums = [1, 2, 3] et N = 4

d = [1, 0, 0, 0, 0] → 1 façon d’obtenir 0 et zéro pour toutes les autres valeurs

i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0

i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0

i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]

i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]

print(d[4]) → affiche 7

Challenge - Dice Combinations

Lorsque vous lancez un dé, vous obtenez un nombre compris entre 1 et 6. Vous devez déterminer le nombre de façons de parvenir au total n en additionnant les résultats de plusieurs lancers de dé.

Entrée

L’entrée contient un seul entier n (1 ≤ n ≤ ).

Sortie

Le programme doit afficher le nombre de façons de lancer un dé pour obtenir la somme n. Étant donné que le résultat peut devenir très grand, il faut l’imprimer modulo .

Exemples

Input	Output
2	2
3	4

Explication

2 → 1 + 1, 2

3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3

Challenge - Dice Combinations

Entrée

Sortie

Exemples

Explication

Constraints

To check your solution you need to sign in

Sign in to continue