leetcode

commit f4227ac904a43e34867d485f76976c700dfb1488
parent 59bb9742720b8a263fb022d83c6a0528d89ae729
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Feb 2023 13:21:33 +0100

Dynamic Programming I: Day 21 FINISH

Diffstat:
A
Problems/0343.cpp
 | 
13
+++++++++++++
A
Problems/0377.cpp
 | 
13
+++++++++++++
M
README.md
 | 
2
++

3 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/0343.cpp b/Problems/0343.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+  int integerBreak(int n) {
+    if (n == 2) return 1;
+    if (n == 3) return 2;
+
+    if (n % 3 == 0)
+      return pow(3, n / 3);
+    else if (n % 3 == 1)
+      return pow(3, n / 3 - 1) * 4;
+    return pow(3, n / 3) * (n % 3);
+  }
+};
diff --git a/Problems/0377.cpp b/Problems/0377.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+  int combinationSum4(vector<int> &nums, int target) {
+    vector<long long> dp(target + 1, 0);
+    dp[0] = 1;
+
+    for (int i = 1; i <= target; i++)
+      for (int num : nums)
+        if (i - num >= 0) dp[i] = (dp[i] + dp[i - num]) % INT_MAX;
+
+    return dp.back();
+  }
+};
diff --git a/README.md b/README.md
@@ -181,6 +181,7 @@ for solving problems.
 |  0334  |   Medium   | [Increasing Triplet Subsequence](Problems/0334.cpp)                                              |
 |  0338  |    Easy    | [Counting Bits](Problems/0338.cpp)                                                               |
 |  0342  |    Easy    | [Power of Four](Problems/0342.cpp)                                                               |
+|  0343  |   Medium   | [Integer Break](Problems/0343.cpp)                                                               |
 |  0344  |    Easy    | [Reverse String](Problems/0344.cpp)                                                              |
 |  0345  |    Easy    | [Reverse Vowels of a String](Problems/0345.cpp)                                                  |
 |  0347  |   Medium   | [Top K Frequent Elements](Problems/0347.cpp)                                                     |
@@ -188,6 +189,7 @@ for solving problems.
 |  0352  |    Hard    | [Data Stream as Disjoint Intervals](Problems/0352.cpp)                                           |
 |  0374  |    Easy    | [Guess Number Higher or Lower](Problems/0374.cpp)                                                |
 |  0376  |   Medium   | [Wiggle Subsequence](Problems/0376.cpp)                                                          |
+|  0377  |   Medium   | [Combination Sum IV](Problems/0377.cpp)                                                          |
 |  0383  |    Easy    | [Ransom Note](Problems/0383.cpp)                                                                 |
 |  0387  |    Easy    | [First Unique Character in a String](Problems/0387.cpp)                                          |
 |  0392  |    Easy    | [Is Subsequence](Problems/0392.cpp)                                                              |