From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 03_dynamic_programming/removing_digits_1637.cpp | 28 +++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 03_dynamic_programming/removing_digits_1637.cpp (limited to '03_dynamic_programming/removing_digits_1637.cpp') diff --git a/03_dynamic_programming/removing_digits_1637.cpp b/03_dynamic_programming/removing_digits_1637.cpp new file mode 100644 index 0000000..8b5b334 --- /dev/null +++ b/03_dynamic_programming/removing_digits_1637.cpp @@ -0,0 +1,28 @@ +#include +#include +#include + +static constexpr int inf = 1999999999; + +std::vector digits(int n) { + std::vector d; + for (int i = n; i != 0; i /= 10) + d.push_back(i % 10); + return d; +} + +int f(std::vector& a, int n) { + if (a[n] != inf) return a[n]; + for (auto d : digits(n)) + if (d != 0) + a[n] = std::min(a[n], 1+f(a, n-d)); + return a[n]; +} + +int main() { + int n; + std::cin >> n; + std::vector a(n+1, inf); + a[0] = 0; + std::cout << f(a, n) << "\n"; +} -- cgit v1.3