На каждом шаге выберите любую ненулевую десятичную цифру, которая присутствует в текущем числе, и вычтите её. После каждого шага цифры берутся из нового значения. Найдите минимальное количество шагов, необходимых для получения нуля.
Реализуйте функцию removing_digits(n).
Входные данные
n: Положительное начальное число.
Выходные данные
Верните минимальное количество шагов вычитания.
Ограничения
1 ≤ n ≤ 1 000 000. Вычитание нуля не считается допустимым ходом и исключается.
Примеры
Ввод:
n = 14
Ожидаемый вывод:
expected = 3Ввод:
long long n = 14;
Ожидаемый вывод:
long long expected = 3;Ввод:
long n = 14;
Ожидаемый вывод:
long expected = 3;Пояснение
14 → 10 → 9 → 0 — три шага. Ни одно из возможных первых вычитаний не позволяет достичь нуля за два шага.
Ввод:
n = 7
Ожидаемый вывод:
expected = 1Ввод:
long long n = 7;
Ожидаемый вывод:
long long expected = 1;Ввод:
long n = 7;
Ожидаемый вывод:
long expected = 1;Пояснение
Вычтите единственную цифру, 7, чтобы сразу получить 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Каждое число зависит от лучшего ответа для меньших чисел, достижимых вычитанием одной цифры.
Подсказка 2
Динамическое программирование по всем значениям до n избавляет от повторных вычислений.
Подсказка 3
Помните, что после каждого вычитания доступные цифры меняются, а 0 никогда не бывает допустимым выбором.
Ожидаемая сложность
O(n * d) по времени, O(n) доп. памяти
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.