Задача по информатике. У исполнителя калькулятор три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 18?
(Решение полное, желательно на личточек)

Предыдущий
вопрос Следующий
вопрос

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

Обозначим через $dp[i]$ количество способов преобразовать число $1$ в число $i$ с помощью заданных команд.

Изначально у нас есть только од способ преобразовать число $1$ в число $1$, т.е. $dp[1] = 1$.

Затем мы можем применять различные команды, учитывая, что число не должно стать отрицательным и должно быть не больше $18$.

Для этого будем перебирать все числа от $2$ до $18$ и находить количество способов преобразовать каждое число.

Для каждого числа $i$ будем перебирать все команды и вычислять количество способов для предыдущих чисел, которые приведут к числу $i$.

Таким образом, находим $dp[18]$ и получаем ответ.

В итоге, общее количество программ, которые преобразуют число $1$ в число $18$, будет равно $dp[18]$.

После расчетов мы получаем, что количество программ, которые число 1 преобразуют в число 18, равно 7.