another implementation for "Coin Change"

haoel · haoel · commit 8469352740f8 · 2016-01-26T23:25:41.000+08:00
diff --git a/algorithms/cpp/coinChange/coinChange.cpp b/algorithms/cpp/coinChange/coinChange.cpp
@@ -1,5 +1,5 @@
 // Source : https://leetcode.com/problems/coin-change/
-// Author : Calinescu Valentin
+// Author : Calinescu Valentin, Hao Chen
 // Date   : 2015-12-28
 
 /*************************************************************************************** 
@@ -60,3 +60,24 @@ class Solution {
             return -1;
     }
 };
+
+
+//Another DP implmentation, same idea above 
+class Solution {
+public:
+    int coinChange(vector<int>& coins, int amount) {
+        const int MAX = amount +1;
+        vector<int> dp(amount+1, MAX);
+        dp[0]=0;
+        
+        for(int i=1; i<=amount; i++) {
+            for (int j=0; j<coins.size(); j++){
+                if (i >= coins[j]) {
+                    dp[i] = min( dp[i], dp[i-coins[j]] + 1 );
+                }
+            }
+        }
+
+        return dp[amount]==MAX ? -1 : dp[amount];
+    }
+};
