_322.cpp added (Coin change DP solution)

anushkagurj · anushkagurj · commit 821cd6f5eb39 · 2020-10-16T13:59:05.000+05:30
diff --git a/cpp/_322.cpp b/cpp/_322.cpp
@@ -0,0 +1,20 @@
+// coin-change
+// Problem Statement: https://leetcode.com/problems/coin-change/
+
+class Solution{
+public:
+    int coinChange(vector<int>& coins, int amount){
+        
+        int MAX = amount + 1;
+        vector<int> cache(amount + 1, MAX);
+        
+        cache[0] = 0;
+        for(auto coin : coins){
+            for(int i = coin; i <= amount; i++)
+                cache[i] = std::min(cache[i], cache[i - coin] + 1);
+        }
+        
+        return cache[amount] == MAX ? -1 : cache[amount];
+    }
+};
+
