leetcode

commit b39a7accfd5b553bda3c07da9be621450f1a3c38
parent 9a21df3f3c06fa914265571633c3fb5407bbe8f4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  7 Oct 2023 15:57:22 +0000

Daily Problem

Diffstat:
A
Problems/1420.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 62 insertions(+), 0 deletions(-)
diff --git a/Problems/1420.cpp b/Problems/1420.cpp
@@ -0,0 +1,61 @@
+
+// Top-down
+class Solution {
+    static const int MOD = 1e9 + 7;
+    static int dp[51][101][51];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int numOfArrays(const int n, const int m, int k, int c = 0, int maxi = 0) {
+        if (c == n) return k == 0;
+        if (k < 0) return 0;
+        if (dp[c][maxi][k] != -1) return dp[c][maxi][k];
+
+        int res = 0;
+        for (int i = 1; i <= maxi; i++) {
+            res = (res + numOfArrays(n, m, k, c + 1, maxi)) % MOD;
+        }
+
+        for (int i = maxi + 1; i <= m; i++) {
+            res = (res + numOfArrays(n, m, k - 1, c + 1, i)) % MOD;
+        }
+
+        return dp[c][maxi][k] = res;
+    }
+};
+
+int Solution::dp[51][101][51];
+
+// Bottom-up
+class Solution {
+    static const int MOD = 1e9 + 7;
+
+  public:
+    int numOfArrays(const int n, const int m, int k) {
+        vector<vector<int>> dp(vector(m + 1, vector(k + 1, 0)));
+        vector<vector<int>> pdp(vector(m + 1, vector(k + 1, 0)));
+        for (int num = 0; num <= m; num++)
+            pdp[num][0] = 1;
+
+        for (int i = n - 1; i >= 0; i--) {
+            for (int maxi = m; maxi >= 0; maxi--) {
+                for (int remain = 0; remain <= k; remain++) {
+                    int res = 0;
+                    for (int num = 1; num <= maxi; num++) {
+                        res = (res + pdp[maxi][remain]) % MOD;
+                    }
+
+                    if (remain > 0) {
+                        for (int num = maxi + 1; num <= m; num++) {
+                            res = (res + pdp[num][remain - 1]) % MOD;
+                        }
+                    }
+
+                    dp[maxi][remain] = res;
+                }
+            }
+            pdp = dp;
+        }
+        return dp[0][k];
+    }
+};
diff --git a/README.md b/README.md
@@ -606,6 +606,7 @@ for solving problems.
 |  1415  |   Medium   | [The k-th Lexicographical String of All Happy Strings of Length n](Problems/1415.cpp)              |
 |  1416  |    Hard    | [Restore The Array](Problems/1416.cpp)                                                             |
 |  1418  |   Medium   | [Display Table of Food Orders in a Restaurant](Problems/1418.cpp)                                  |
+|  1420  |    Hard    | [Build Array Where You Can Find The Maximum Exactly K Comparisons](Problems/1420.cpp)              |
 |  1425  |    Hard    | [Constrained Subsequence Sum](Problems/1425.cpp)                                                   |
 |  1431  |    Easy    | [Kids With the Greatest Number of Candies](Problems/1431.cpp)                                      |
 |  1433  |   Medium   | [Check If a String Can Break Another String](Problems/1433.cpp)                                    |