UniLecs #126. Строковые комбинации
UniLecs
Задача: вы работаете со строками, у вас есть след.символы: '1', '2', '3'. Необходимо определить кол-во всевозможных строк длины N, ктр состоят только из этих символов, но при этом не содержат подстроку "12".
Входные данные: N - длина строки от 1 до 30.
Вывод: кол-во всевозможных комбинаций строк
Пример: N = 3
Answer = 21
Идея: вспоминаем старую добрую динамику (ДП - динамическое программирование).
Пусть d(n) - кол-во всевозможных строковых комбинаций для строки длиной N.
Разберем частные случаи для N = 1 и N = 2.
1. N = 1: тут все просто, строка из 1 символа, кол-во таких строк равно 3.
d(1) = 3
2. N = 2: получим след.строки:
"11", "21", "31"
"13", "22", "32",
"23", "33"
Получаем d(2) = 8
3. Теперь попробуем вывести общий случай для случая N = n.
Первым символом можно выбрать любой из 3х символов: '1', '2', '3':
а. Если для 1го символа используем '2' или '3', то в след.символах можно использовать любую из d(n - 1) строк. d(n) = 2 * d(n - 1);
b. Если для 1го символа используем '1', то рассматриваем отдельные случаи:
b.1. Если 2й символ - '3', то в след.символах можно использовать любую из d(n - 2) строк.
b.2. Если 2й символ - '1', то для 3го символа снова возвращаемся к пункту b.
Складываем полуенные формулы и получаем формулу для n:
d(n) = 2 * d(n - 1) + d(n - 2) + d(n - 3) + ... + d(1) + d(0).
Что верно для n, то верно и для n-1, поэтому
d(n - 1) = 2 * d(n - 2) + d(n - 3) + d(n - 4) + ... + d(1) + d(0).
Немного преобразуем:
d(n - 1) - d(n - 2) = d(n - 2) + d(n - 3) + d(n - 4) + ... + d(1) + d(0).
Подставим это выражение в 1ю формулу и получим итоговое соотношение:
d(n) = 2 * d(n - 1) + d(n - 1) - d(n - 2) = 3 * d(n - 1) - d(n - 2)
d(n) = 3 * d(n - 1) - d(n - 2)
Реализация:
https://gist.github.com/unilecs/d5fdcd626985664808e3ab6fd4bc1c1b
Test: