Suma de Combinaciones

Dado el valor objetivo N y un arreglo de números positivos permitidos, se pide contar cuántas formas existen de escribir N como la suma de esos números.

Por ejemplo, si los valores permitidos son [1, 2, 3] y el número N es 4, se pueden obtener 7 sumas distintas:

Todas las 7 maneras de sumar 1, 2, 3 para obtener 4

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

Este es un problema clásico de programación dinámica, que se puede resolver manteniendo un estado d[sum], el cual representa todas las formas posibles de obtener el valor sum combinando los números permitidos:

N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = todas las combinaciones que suman i
d[0] = 1                   # Hay 1 forma de obtener 0: no tomar ningún número

for i in range(1, N + 1):  # Intentar obtener todos los valores de 1...N
    for num in nums:       # Tratar de actualizar d[i] con la ayuda de num
        if i - num >= 0:
            d[i] += d[i - num]
print(d[N])

De esta manera, d[i] representa la cantidad de maneras de formar i usando los números en nums. Empezamos todo en 0 excepto d[0], que se asigna a 1 porque solo existe una forma de obtener 0: no usar ningún número permitido. Para los demás valores, consideramos todas las posibles formas que se usan para llegar a ellos.

Por ejemplo, si se puede obtener el número 11 (d[11]) de 5 formas diferentes, y el número 8 (d[8]) de 3 maneras, entonces, si en nums está el número 3, se puede llegar a 11 sumando a esas 3 maneras de llegar a 8 (las de d[8]) el número 3. Así, se amplían las formas de llegar a 11.

Simulemos el algoritmo con el ejemplo:

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

d = [1, 0, 0, 0, 0] → Hay 1 forma de obtener 0 y 0 para el resto

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

i = 2 num = 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 = 3 num = 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 = 4 num = 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]) → imprime 7

Desafío - Combinaciones de dados

Si lanzas un dado, obtienes un número del 1 al 6. Se te pide calcular cuántas formas hay de obtener el número n al sumar los resultados de estas tiradas.

Entrada

La entrada contiene un solo entero n (1 ≤ n ≤ ).

Salida

El programa debe imprimir el número de maneras de lanzar el dado para obtener el número n como suma de esas tiradas. Dado que la respuesta puede ser muy grande, se debe imprimir el resultado con módulo .

Ejemplos

Entrada	Salida
2	2
3	4

Explicación

2 → 1 + 1, 2

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

Desafío - Combinaciones de dados

Entrada

Salida

Ejemplos

Explicación

Constraints

To check your solution you need to sign in

Sign in to continue