問題
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 つずつ開いてみましょう。
ヒント 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用に調整されています。上記の説明と制約に従ってください。