leetcode

commit ecc6491fcaa979b79eba0c6fa274e9d6f3e56379
parent 904ad8f99cda635f793ab15f6f2465ac2e7ab514
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  9 Feb 2023 15:55:09 +0100

Dynamic Programming I: Day 20

Diffstat:
A
Problems/0322.cpp
 | 
16
++++++++++++++++
A
Problems/0518.cpp
 | 
13
+++++++++++++
M
README.md
 | 
2
++

3 files changed, 31 insertions(+), 0 deletions(-)
diff --git a/Problems/0322.cpp b/Problems/0322.cpp
@@ -0,0 +1,16 @@
+// DP solution
+class Solution {
+public:
+  int coinChange(vector<int> &coins, int amount) {
+    vector<int> dp(amount + 1, INT_MAX);
+    dp[0] = 0;
+
+    for (int i = 0; i < amount; i++) {
+      if (dp[i] == INT_MAX) continue;
+      for (int coin : coins)
+        if ((long long)coin + i <= amount)
+          dp[coin + i] = min(dp[coin + i], dp[i] + 1);
+    }
+    return dp[amount] != INT_MAX ? dp[amount] : -1;
+  }
+};
diff --git a/Problems/0518.cpp b/Problems/0518.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+  int change(int amount, vector<int> &coins) {
+    vector<long long> dp(amount + 1, 0);
+    dp[0] = 1;
+
+    for (int coin : coins)
+      for (int i = 0; i <= amount; i++)
+        if (i - coin >= 0) dp[i] += dp[i - coin];
+
+    return (int)dp.back();
+  }
+};
diff --git a/README.md b/README.md
@@ -175,6 +175,7 @@ for solving problems.
 |  0304  |   Medium   | [Range Sum Query 2D - Immutable](Problems/0304.cpp)                                              |
 |  0309  |   Medium   | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp)                               |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                        |
+|  0322  |   Medium   | [Coin Change](Problems/0322.cpp)                                                                 |
 |  0326  |    Easy    | [Power of Three](Problems/0326.cpp)                                                              |
 |  0328  |   Medium   | [Odd Even Linked List](Problems/0328.cpp)                                                        |
 |  0334  |   Medium   | [Increasing Triplet Subsequence](Problems/0334.cpp)                                              |
@@ -220,6 +221,7 @@ for solving problems.
 |  0503  |   Medium   | [Next Greater Element II](Problems/0503.cpp)                                                     |
 |  0509  |    Easy    | [Fibonacci Number](Problems/0509.cpp)                                                            |
 |  0516  |   Medium   | [Longest Palindromic Subsequence](Problems/0516.cpp)                                             |
+|  0518  |   Medium   | [Coin Change II](Problems/0518.cpp)                                                              |
 |  0520  |    Easy    | [Detect Capital](Problems/0520.cpp)                                                              |
 |  0530  |    Easy    | [Minimum Absolute Difference in BST](Problems/0530.cpp)                                          |
 |  0538  |   Medium   | [Convert BST to Greater Tree](Problems/0538.cpp)                                                 |