Динамическое программирование. Задача о счастливых билетах.

Условие

Задача о счастливых билетах: билет состоящий из 2n цифр называется счастливым если сумма первых n цифр равна сумме последних n цифр.

Необходимо посчитать кол-во счастливых билетов например для n=3 (длина билета 6).

Решение

Для решения данной задачи необходимо построить специальную таблицу от n = 1, до необходимого нам n.

Во всех колонка рассматриваются  ячейки от 0 до 9 * n + 1 (n - текущее), для n=1  это 9 * 1 + 1, для n=2 это 9 * 2 + 1=19, и т.д.

• Первая колонка - базовый случай, заполняется “1”.
• Пустые ячейки это “0”.
• Если k (индекс) меньше 10, то значение ячейки равно сумме первых k ячеек левого столбца.
• Если k >= 10, то значении ячейки равно сумме 10 ячеек левого столбца начиная с k до k-10+1

Ответом является сумма квадратов значений всех ячеек нужного нам столбца

(Чтобы быстро создать таблицу)

1. базовый случай, первая строка все “1”, первый столбец 1 * 9 + 1= 10 единиц
2. первые 10 строк (от 0 до 9 цифры)  для любого n, это сумма левой + верхней ячейки
3. начиная с k=10, значение ячейки равно сумме значений ячейки слева и ещё 9 ячеек вверх.  (сумма от k-10+1 до k)