Алгоритмы и структуры данных

Сумма комбинаций (Combination Sum)

Задано целевое значение N и массив допустимых положительных чисел. Необходимо определить количество способов представить N в виде суммы из этих чисел.
Например, если в качестве допустимых значений взять [1, 2, 3], а число N равно 4, то существует 7 разных способов сложить эти числа, чтобы получить 4:
Все 7 способов сложить 1, 2, 3, чтобы получить 4
  1. 1 + 1 + 1 + 1
  1. 1 + 1 + 2
  1. 1 + 2 + 1
  1. 2 + 1 + 1
  1. 1 + 3
  1. 3 + 1
  1. 2 + 2
Это классическая задача динамического программирования, которую можно решить путём хранения состояния d[sum], отражающего все возможные способы получить сумму sum из разрешённых чисел:
N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = все комбинации, которые в сумме дают i
d[0] = 1                   # Существует 1 способ получить 0 – не брать ни одного числа

for i in range(1, N + 1):  # Пытаемся вычислить d[i] последовательно для i от 1 до N
    for num in nums:       # Пробуем получить d[i] с помощью num
        if i - num >= 0:   # Проверяем, возможно ли сформировать i из num
            d[i] += d[i - num]
print(d[N])
Таким образом, наше состояние d[i] — это количество способов получить i, используя допустимые числа из nums. Изначально все значения обнуляются, кроме d[0], которое выставляется равным 1, поскольку мы можем получить 0 единственным способом — не используя ни одного числа. Для всех остальных чисел мы последовательно перебираем все разрешённые варианты из nums.
Если, к примеру, мы можем получить число 11 (d[11]) 5 разными способами и знаем, что число 8 (d[8]) мы могли получить 3 разными способами, то при наличии в nums числа 3 мы можем сформировать 11 всеми найденными ранее способами плюс всеми способами получения 8 (d[8]), добавив в конце число 3.
Давайте прогоним алгоритм на примере:
nums = [1, 2, 3] и N = 4
  1. d = [1, 0, 0, 0, 0] → 1 способ получить 0, остальные пока равны 0
  1. i = 1 num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
  1. 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
  1. 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]
  1. 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]
  1. print(d[4]) → выводит 7
 

Задание – Комбинации с кубиком (Dice Combinations)

Если вы бросаете игральную кость, она может выдать число от 1 до 6. Нужно вычислить, сколькими способами можно получить число n, суммируя результаты бросков.
notion image

Входные данные

Во входных данных дано одно целое число n (1 ≤ n ≤ ).

Выходные данные

Программа должна вывести количество способов, которыми можно набрать сумму n, последовательно бросая кость. Поскольку ответ может быть очень большим, нужно напечатать его по модулю .

Примеры

Input
Output
2
2
3
4

Пояснение

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

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue