0518-coin-change-ii.md Added 7 languages' solutions.

gazeldx · gazeldx · commit 56c6a851684e · 2024-12-03T19:46:29.000+08:00
diff --git a/README.md b/README.md
@@ -23,9 +23,12 @@ After finishing one category of questions, you can study another category to imp
 - [392. Is Subsequence](problems/0392-is-subsequence.md)
 - [583. Delete Operation for Two Strings](problems/0583-delete-operation-for-two-strings.md)
 - [72. Edit Distance](problems/0072-edit-distance.md)
+
+### Knapsack problems
 - [416. Partition Equal Subset Sum](problems/0416-partition-equal-subset-sum.md)
 - [1049. Last Stone Weight II](problems/1049-last-stone-weight-ii.md)
 - [494. Target Sum](problems/0494-target-sum.md)
 - [474. Ones and Zeroes](problems/0474-ones-and-zeroes.md)
+- [518. Coin Change II](problems/0518-coin-change-ii.md)
 
 - More LeetCode problems will be added soon...
diff --git a/problems/0518-coin-change-ii.md b/problems/0518-coin-change-ii.md
@@ -0,0 +1,170 @@
+# 518. Coin Change II
+LeetCode problem: [518. Coin Change II](https://leetcode.com/problems/coin-change-ii/)
+
+## LeetCode problem description
+> You are given an integer array `coins` representing coins of different denominations and an integer amount representing a total `amount` of money.
+
+Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return `0`.
+
+You may assume that you have an infinite number of each kind of coin.
+
+The answer is **guaranteed** to fit into a signed 32-bit integer.
+
+```
+Example 1:
+
+Input: amount = 5, coins = [1,2,5]
+Output: 4
+
+Explanation: there are four ways to make up the amount:
+5=5
+5=2+2+1
+5=2+1+1+1
+5=1+1+1+1+1
+------------------------------------------------------------------------
+
+Example 2:
+
+Input: amount = 3, coins = [2]
+Output: 0
+
+Explanation: the amount of 3 cannot be made up just with coins of 2.
+------------------------------------------------------------------------
+
+Example 3:
+
+Input: amount = 10, coins = [10]
+Output: 1
+------------------------------------------------------------------------
+
+Constraints:
+
+1 <= coins.length <= 300
+1 <= coins[i] <= 5000
+All the values of 'coins' are unique.
+0 <= amount <= 5000
+```
+
+## Thoughts
+It is a `Unbounded Knapsack Problem`.
+
+### Complexity
+* Time: `O(n * m)`.
+* Space: `O(n)`.
+
+## Python
+```python
+class Solution:
+    def change(self, amount: int, coins: List[int]) -> int:
+        dp = [0] * (amount + 1)
+        dp[0] = 1
+        
+        for coin in coins:
+            for j in range(coin, len(dp)):
+                dp[j] += dp[j - coin]
+
+        return dp[-1]
+```
+
+## C++
+```cpp
+class Solution {
+public:
+    int change(int amount, vector<int>& coins) {
+        auto dp = vector<unsigned int>(amount + 1, 0);
+        dp[0] = 1;
+
+        for (auto coin : coins) {
+            for (auto j = coin; j < dp.size(); j++) {
+                dp[j] += dp[j - coin];
+            }
+        }
+
+        return dp.back();
+    }
+};
+```
+
+## Java
+```java
+class Solution {
+    public int change(int amount, int[] coins) {
+        var dp = new int[amount + 1];
+        dp[0] = 1;
+
+        for (var coin : coins) {
+            for (var j = coin; j < dp.length; j++) {
+                dp[j] += dp[j - coin];
+            }
+        }
+
+        return dp[dp.length - 1];
+    }
+}
+```
+
+## C#
+```c#
+public class Solution {
+    public int Change(int amount, int[] coins) {
+        var dp = new int[amount + 1];
+        dp[0] = 1;
+
+        foreach (var coin in coins) {
+            for (var j = coin; j < dp.Length; j++) {
+                dp[j] += dp[j - coin];
+            }
+        }
+
+        return dp.Last();
+    }
+}
+```
+
+## JavaScript
+```javascript
+var change = function(amount, coins) {
+   const dp = Array(amount + 1).fill(0)
+   dp[0] = 1
+
+   for (const coin of coins) {
+      for (let j = coin; j < dp.length; j++) {
+         dp[j] += dp[j - coin]
+      }
+   }
+
+   return dp.at(-1);
+};
+```
+
+## Go
+```go
+func change(amount int, coins []int) int {
+    dp := make([]int, amount + 1)
+    dp[0] = 1
+
+    for _, coin := range coins {
+        for j := coin; j < len(dp); j++ {
+            dp[j] += dp[j - coin]
+        }
+    }
+
+    return dp[len(dp) - 1]
+}
+```
+
+## Ruby
+```ruby
+def change(amount, coins)
+  dp = Array.new(amount + 1, 0)
+  dp[0] = 1
+
+  coins.each do |coin|
+    (coin...dp.size).each do |j|
+      dp[j] += dp[j - coin]
+    end
+  end
+
+  dp[-1]
+end
+```
