DSA sheet / Dynamic programming
Removing Digits
Do these first: Minimizing Coins
The problem in brief
Starting from an integer n (up to a million), each step subtracts one digit that appears in the current number from that number. Print the minimum number of steps needed to reach 0.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1637.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
The obvious idea is to always subtract the biggest digit. Test it on a few numbers, for example 27 by hand and by exhaustive search. Does greedy always win?
-
Model the numbers 0..n as nodes and each allowed subtraction as an edge. What are you computing on that graph?
-
Every edge goes from a bigger number to a smaller one. What does that tell you about a safe order in which to compute answers?
-
Define steps[v] as the minimum steps from v down to 0 and write it in terms of steps of smaller numbers. Remember not to subtract a zero digit.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
First test the tempting greedy (always subtract the largest digit). Greedy often works here but you should not rely on an unproved rule; a DP is simple enough that it does not need the risk. The transferable step is recognising a shortest path in a graph whose edges always point to smaller values: that is a DAG, so DP in increasing order of the value is a valid topological order.
State: steps[v] = fewest steps from v to 0. Transition: for each nonzero digit d of v, steps[v] = 1 + steps[v - d], minimised over all digits. Base: steps[0] = 0. A digit of 0 would produce a self-loop (v - 0 = v), which is useless and would break the recurrence, so skip it.
The habit: when a “minimum number of moves” problem has moves that strictly decrease some quantity, it is a DP over that quantity.
Intuition
Think of the numbers as floors in a building and each number as offering elevators that drop by exactly its own digits. You want the fewest elevator rides from floor n down to the ground. Work from the ground up: the answer for each floor uses answers you already computed for lower floors.
Approach
- Create steps[0..n] with steps[0] = 0.
- For v from 1 to n: extract the digits of v; for each nonzero digit d, take steps[v] = min(steps[v], steps[v - d] + 1).
- Print steps[n].
Pitfalls: skip zero digits; every v >= 1 has at least one nonzero digit, so steps[v] is always defined; digit extraction is a tiny inner loop (at most 7 digits for n = 10^6).
Complexity
O(n * digits) time, about 7 * 10^6 operations, and O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> steps(n + 1, 0);
for (int v = 1; v <= n; v++) {
int best = INT_MAX;
for (int t = v; t > 0; t /= 10) {
int d = t % 10;
if (d > 0) best = min(best, steps[v - d] + 1);
}
steps[v] = best;
}
printf("%d\n", steps[n]);
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
steps = [0] * (n + 1)
for v in range(1, n + 1):
best = 10**9
t = v
while t > 0:
d = t % 10
if d and steps[v - d] + 1 < best:
best = steps[v - d] + 1
t //= 10
steps[v] = best
print(steps[n])
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
int[] steps = new int[n + 1];
for (int v = 1; v <= n; v++) {
int best = Integer.MAX_VALUE;
for (int t = v; t > 0; t /= 10) {
int d = t % 10;
if (d > 0) best = Math.min(best, steps[v - d] + 1);
}
steps[v] = best;
}
System.out.println(steps[n]);
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
const steps = new Int32Array(n + 1);
for (let v = 1; v <= n; v++) {
let best = 1e9;
for (let t = v; t > 0; t = Math.floor(t / 10)) {
const d = t % 10;
if (d > 0 && steps[v - d] + 1 < best) best = steps[v - d] + 1;
}
steps[v] = best;
}
console.log(steps[n]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).