Problem
Wähle in jedem Schritt eine aktuell im Zahlwert vorhandene, von Null verschiedene Dezimalziffer und subtrahiere diese Ziffer. Nach jedem Schritt werden die Ziffern aus dem neuen Wert entnommen. Finde die minimale Anzahl an Schritten, um Null zu erreichen.
Implementiere removing_digits(n).
Eingabe
n: Die positive Startzahl.
Ausgabe
Gib die geringste Anzahl an Subtraktionsschritten zurück.
Einschränkungen
1 ≤ n ≤ 1.000.000. Das Subtrahieren von Null ist kein zulässiger Zug und ausgeschlossen.
Beispiele
Eingabe:
n = 14
Erwartete Ausgabe:
expected = 3Eingabe:
long long n = 14;
Erwartete Ausgabe:
long long expected = 3;Eingabe:
long n = 14;
Erwartete Ausgabe:
long expected = 3;Erläuterung
14 → 10 → 9 → 0 benötigt drei Schritte. Keine der möglichen ersten Subtraktionen erreicht Null in nur zwei Schritten.
Eingabe:
n = 7
Erwartete Ausgabe:
expected = 1Eingabe:
long long n = 7;
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long n = 7;
Erwartete Ausgabe:
long expected = 1;Erläuterung
Subtrahiere die einzige Ziffer, 7, um sofort 0 zu erreichen.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jede Zahl hängt von der besten Antwort für kleinere Zahlen ab, die durch das Entfernen einer Ziffer erreichbar sind.
Hinweis 2
Dynamic Programming über alle Werte bis n vermeidet doppelte Arbeit.
Hinweis 3
Denk daran, dass sich die verfügbaren Ziffern nach jeder Subtraktion ändern, und 0 ist nie eine gültige Wahl.
Erwartete Komplexität
Zeit O(n * d), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.