Условие
At each step, choose a nonzero decimal digit currently present in the number and subtract that digit. Digits are taken from the new value after every step. Find the minimum number of steps needed to reach zero.
Implement removing_digits(n).
Input
n: The positive starting number.
Output
Return the fewest subtraction steps.
Ограничения
1 ≤ n ≤ 1,000,000. Subtracting zero is not a useful move and is excluded.
Примеры
Ввод:
n = 14
Ожидаемый вывод:
expected = 3Ввод:
long long n = 14;
Ожидаемый вывод:
long long expected = 3;Ввод:
long n = 14;
Ожидаемый вывод:
long expected = 3;Пояснение
14 → 10 → 9 → 0 uses three steps. Neither possible first subtraction can reach zero in only two steps.
Ввод:
n = 7
Ожидаемый вывод:
expected = 1Ввод:
long long n = 7;
Ожидаемый вывод:
long long expected = 1;Ввод:
long n = 7;
Ожидаемый вывод:
long expected = 1;Пояснение
Subtract the only digit, 7, to reach 0 immediately.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Each number depends on the best answer for smaller numbers reachable by subtracting one digit.
Подсказка 2
Dynamic programming over all values up to n avoids repeated work.
Подсказка 3
Remember that the available digits change after every subtraction, and zero is never a valid choice.
Ожидаемая сложность
O(n * d) time, O(n) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.