ゼロにするための桁引き算

問題

各ステップで、現在の数に含まれる0以外の10進数の桁を1つ選び、その桁を引きます。毎回、引き算後の新しい値から桁を選びます。ゼロに到達するまでに必要な最小ステップ数を求めてください。

removing_digits(n) を実装してください。

n: 正の開始数値。

最小の引き算ステップ数を返してください。

1 ≤ n ≤ 1,000,000。0を引く操作は意味がないため除外されます。

例 1

入力：
n = 14

期待される出力：
expected = 3

入力：
long long n = 14;

期待される出力：
long long expected = 3;

入力：
long n = 14;

期待される出力：
long expected = 3;

14 → 10 → 9 → 0 の3ステップが必要です。どちらの最初の引き算でも、2ステップでゼロに到達することはできません。

例 2

入力：
n = 7

期待される出力：
expected = 1

入力：
long long n = 7;

期待される出力：
long long expected = 1;

入力：
long n = 7;

期待される出力：
long expected = 1;

唯一の桁である7を引くことで、すぐに0になります。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各数は、1桁引いて到達できる小さい数の最適解に依存します。

ヒント 2

nまでの全ての値で動的計画法を使えば、重複計算を避けられます。

ヒント 3

引くたびに使える桁が変わること、0は有効な選択ではないことに注意します。

目安の計算量

時間 O(n * d)、追加メモリ O(n)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。