Solved a dp problem on codeforces

1 files changed, 31 insertions, 0 deletions

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';
+}