Разберём решение ещё одной задачи на динамическое программирование, в которой нет ничего сложного, и можно рассмотреть все шаги решения таких задач. Сначала читаем условие:
Алгоритм решения будет точно таким же, как и в задачах Задача 11. Зайчик и Задача 29. Компьютерная игра. Но здесь есть дополнительные ограничения, поэтому рекомендую разобраться с теми задачами и потом вернуться сюда.
Как обычно, сначала надо определиться, что будет состоянием динамики.
Выберем в качестве состояния длину префикса введённого числа. И для каждого префикса посчитаем, сколько есть вариантов его разделить, согласно условиям задачи.
Вторая часть - это составление рекуррентного соотношения. Его можно получить, если ответить на вопрос: "Как можно получить состояние i?" или в нашем случае: "Как получается префикс длины i?". Ответ простой:
- из префикса длины i-1 добавлением однозначного числа или
- из префикса длины i-2 добавлением двузначного числа, или
- из префикса длины i-3 добавлением трёхзначного числа
- и так далее, пока добавляемое число не больше C.
Третья составляющая - база динамики. Тут совсем просто - префикс длины 0 можно получить одним способом.
Давайте теперь запишем это решение. Считываем входные данные и числа сразу приводим к числовому типу, а результат работы Вовиной программы оставляем строкой:
Заведём список для хранения ответов и сразу же положим в него единицу в качестве базы:
Теперь пройдём по всей строке, и для каждого префикса вычислим ответ. Так как ответом будет сумма всех возможных вариантов, то инициализируем переменную нулём:
В цикле переберём варианты однозначного, двузначного и так далее чисел до девятизначного (так как по условию задачи число С имеет не больше цифр). И для каждого варианта проверим, что добавляемое число не начинается с нуля и не превышает С:
Все подходящие варианты суммируем в а, которую потом добавляем к списку с результатами, оставив К цифр.
Ответом будет последнее число, потому что оно отвечает за префикс длины N, то есть всю строку:
Решили задачу за O(N), но тут есть несколько тяжёлых операций:
- перевод строки в число,
- возведение числа в степень.
Поэтому решение на Python работает не очень быстро, но тем не менее укладывается в рамки с двукратным запасом.
Хорошая задача для продолжающих изучать динамическое программирование.
Предыдущий выпуск: Задача 535. Неправильное сложение
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.