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

Question

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

Risa Clar Знаток (363), закрыт 4 года назад

Задача 5 - Карточки для счета (100 баллов)
Полный балл: 100
Ограничение времени: 1 с
Ограничение памяти: 128M
Юный программист Петя обучает своего младшего брата арифметике. Петя заготовил много карточек, на каждой из которых написана одна из цифр от 0 до 9 включительно. Петя решил что будет выкладывать карточки в ряд, а младший брат будет просматривать карточки слева направо, складывать цифры на двух соседних карточках и называть ответ. Например, если бы Петя выложил такую последовательность карточек: 2 3 4 1 2, то брат должен был бы назвать вот такую последовательность ответов: 5, 7, 5, 3.
Хотя Петя и любит арифметику, он все же решил сильно не нагружать брата, и выкладывать такие последовательности карточек, чтобы сумма на любых двух соседних карточках не превосходила некоторое число S. С другой стороны, Петя волнуется, а не слишком ли мало заданий получится для брата?
Напишите программу, которая посчитает количество различных последовательностей длины N, состоящих из цифр от 0 до 9 таких, что сумма двух соседних цифр в последовательности не превышает заданного числа S.
Формат входных данных
Ввод содержит два числа N (2 ≤ N ≤ 100) и S (0 ≤ S ≤ 18), разделенные пробелом - количество цифр в последовательности, и максимально возможное значение суммы двух соседних цифр в последовательности.
Формат результата
Выведите единственное число - количество различных последовательностей из цифр длины N, в которых сумма любых двух соседних цифр не превосходит S.
Примеры
Входные данные
3 1
Результат работы
5
Входные данные
3 2
Результат работы
14
Примечания
Последовательностей длины 3 таких, что сумма соседних элементов не превосходит 1, всего 5:
0 0 0
0 0 1
0 1 0
1 0 0
1 0 1

Помогите пожалуйста, мне вообще ничего не понятно.

Answer 1

Вообщем задаешь 2 переменные. Длина последовательности и число, которое 2 лежащих рядом элемента не должны превышать.
Самый простой способ решить - тупо перебрать все последовательности длины N и пройтись по ним - проверяя все соседние элементы на то, чтобы были меньше или равны S. Но ты можешь не уложиться в секунду
А откуда у тебя эта задачка, это вам в колледже такие задают?
UPD: Может знание комбинаторики поможет

Answer 2

Динамическое программирование.
f[i,d] - количество способов составить число длины i с цифрой d на конце.
Начальные условия - f[1,0] = f[1,1] = ...= f[1, 9] = 1.
Переход - f[i, d] -> f[i+1, 0], f[i+1, 1], ..f[i+1, S - d].
Ответ - сумма f[N, 0] + .+ f[N, 9].