Хорошим будем называть натуральное число, все цифры которого (в десятичной записи) различные, идут в порядке возрастания, считая от разряда единиц к старшим разрядам, и среди которых нет четырех идущих подряд (например, 3, 4, 5 и 6 не должны присутствовать в хорошем числе одновременно). Сколько существует хороших чисел, записываемых цифрами от 1 до 8?

Для решения задачи мы можем использовать метод динамического программирования. Для каждой длины числа от 1 до 8 мы будем подсчитывать количество хороших чисел.

Шаги решения:
1. Инициализируем массив dp длины 9 (от 0 до 8) нулями. Этот массив будет хранить количество хороших чисел для каждой длины.
2. Заполняем базовые значения в массиве dp: dp[1] = 8 (так как есть 8 однозначных чисел от 1 до 8).
3. Запускаем цикл от 2 до 8, где i – текущая длина числа.
4. Внутри цикла перебираем все возможные последние цифры чисел от 1 до 8, и для каждой последней цифры обновляем значение dp[i].
5. Для каждой последней цифры сравниваем ее со всеми предыдущими цифрами числа. Если последняя цифра больше предыдущей и их разность составляет не менее 2, то мы можем добавить это число к dp[i], так как оно будет удовлетворять условиям хорошего числа.
6. После перебора всех возможных последних цифр, dp[i] будет содержать количество хороших чисел длины i.
7. Выводим значение dp[8] как ответ.

Ответ: количество хороших чисел, записываемых цифрами от 1 до 8, равно dp[8].