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/edit_distance_1639.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 03_dynamic_programming/edit_distance_1639.cpp (limited to '03_dynamic_programming/edit_distance_1639.cpp') diff --git a/03_dynamic_programming/edit_distance_1639.cpp b/03_dynamic_programming/edit_distance_1639.cpp new file mode 100644 index 0000000..0d8c6ef --- /dev/null +++ b/03_dynamic_programming/edit_distance_1639.cpp @@ -0,0 +1,22 @@ +#include +#include +#include +#include + +int d(const std::string& a, const std::string& b, size_t i, size_t j, + std::vector>& t) { + if (t[i][j] != -1) return t[i][j]; + if (i == a.size()) return t[i][j] = b.size()-j; + if (j == b.size()) return t[i][j] = a.size()-i; + if (a[i] == b[j]) return t[i][j] = d(a, b, i+1, j+1, t); + return t[i][j] = 1+std::min(d(a, b, i+1, j+1, t), + std::min(d(a, b, i+1, j, t), d(a, b, i, j+1, t))); +} + +int main() { + std::string a, b; + std::cin >> a >> b; + std::vector> + t(a.size()+1, std::vector(b.size()+1, -1)); + std::cout << d(a, b, 0, 0, t) << "\n"; +} -- cgit v1.3