From 035ae0db488809f8c6a2d0956614c344ed8e4f32 Mon Sep 17 00:00:00 2001
From: omagdy7 <omar.professional8777@gmail.com>
Date: Tue, 7 Mar 2023 16:21:15 +0200
Subject: Solved a dp problem on codeforces

---
 classics/dp/coin             | Bin 0 -> 59536 bytes
 classics/dp/coin.cpp         |  31 +++++++++++++++++++++++++++++++
 classics/dp/coin_input0.txt  |   1 +
 classics/dp/coin_output0.txt |   1 +
 4 files changed, 33 insertions(+)
 create mode 100755 classics/dp/coin
 create mode 100644 classics/dp/coin.cpp
 create mode 100644 classics/dp/coin_input0.txt
 create mode 100644 classics/dp/coin_output0.txt

(limited to 'classics/dp')

diff --git a/classics/dp/coin b/classics/dp/coin
new file mode 100755
index 0000000..be286f0
Binary files /dev/null and b/classics/dp/coin differ
diff --git a/classics/dp/coin.cpp b/classics/dp/coin.cpp
new file mode 100644
index 0000000..cc57f02
--- /dev/null
+++ b/classics/dp/coin.cpp
@@ -0,0 +1,31 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+vector<int> coins = {1, 3, 4};
+#define INF 1e9
+
+int solve(int x) {
+  static map<int, int> cache;
+  if (x < 0)
+    return INF;
+  if (x == 0) {
+    cache[0] = 0;
+    return 0;
+  }
+  if (cache.count(x)) {
+    return cache[x];
+  }
+  int best = INF;
+  for (auto c : coins) {
+    best = min(best, solve(x - c) + 1);
+  }
+  cache[x] = best;
+  return best;
+}
+
+int main() {
+  int n;
+  cin >> n;
+  cout << solve(n) << '\n';
+}
diff --git a/classics/dp/coin_input0.txt b/classics/dp/coin_input0.txt
new file mode 100644
index 0000000..9a03714
--- /dev/null
+++ b/classics/dp/coin_input0.txt
@@ -0,0 +1 @@
+10
\ No newline at end of file
diff --git a/classics/dp/coin_output0.txt b/classics/dp/coin_output0.txt
new file mode 100644
index 0000000..e440e5c
--- /dev/null
+++ b/classics/dp/coin_output0.txt
@@ -0,0 +1 @@
+3
\ No newline at end of file
-- 
cgit v1.2.3