Solved a dp problem on codeforces

4 files changed, 33 insertions, 0 deletions

diff --git a/classics/dp/coin b/classics/dp/coin
new file mode 100755
index 0000000..be286f0
--- /dev/null
+++ b/classics/dp/coin
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