added unbounded knapsack problems

AlveeM · AlveeM · commit 40a2fe859c5f · 2021-03-09T15:36:41.000-05:00
diff --git a/dynamic-programming/patterns-dynamic-programming/02-unbounded-knapsack/01_coin_change.py b/dynamic-programming/patterns-dynamic-programming/02-unbounded-knapsack/01_coin_change.py
@@ -0,0 +1,26 @@
+class Solution:
+    def coinChange(self, coins: List[int], amount: int) -> int:
+        n = len(coins)
+        dp = [[float('inf') for _ in range(amount+1)] for _ in range(n+1)]
+        
+        for i in range(n+1):
+            dp[i][0] = 0
+        
+        for i in range(n+1):
+            for j in range(amount+1):
+                if coins[i-1] > j:
+                    dp[i][j] = dp[i-1][j]
+                else:
+                    dp[i][j] = min(1 + dp[i][j-coins[i-1]], dp[i-1][j])
+        
+        return dp[n][amount] if dp[n][amount] != float('inf') else -1
+
+# optimized solution
+class Solution2:
+    def coinChange(self, coins: List[int], amount: int) -> int:
+        dp = [float('inf') for _ in range(amount+1)]
+        dp[0] = 0
+        for coin in coins:
+            for i in range(amount-coin+1):
+                dp[i+coin] = min(dp[i+coin], dp[i]+1)
+        return dp[amount] if dp[amount] != float('inf') else -1
diff --git a/dynamic-programming/patterns-dynamic-programming/02-unbounded-knapsack/02_coin_change_II.py b/dynamic-programming/patterns-dynamic-programming/02-unbounded-knapsack/02_coin_change_II.py
@@ -0,0 +1,17 @@
+class Solution:
+    def change(self, amount: int, coins: List[int]) -> int:
+        n = len(coins)
+        dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]
+        
+        for i in range(n+1):
+            dp[i][0] = 1
+        
+        for i in range(1, n+1):
+            for j in range(amount+1):
+                if j >= coins[i-1]:
+                    dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
+                else:
+                    dp[i][j] = dp[i-1][j]
+        
+        return dp[n][amount]
+                    
