feat: solve No.1420

BaffinLee · BaffinLee · commit e7f7cda8e2ed · 2023-10-08T23:43:15.000+08:00
diff --git a/1401-1500/1420. Build Array Where You Can Find The Maximum Exactly K Comparisons.md b/1401-1500/1420. Build Array Where You Can Find The Maximum Exactly K Comparisons.md
@@ -0,0 +1,107 @@
+# 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
+
+- Difficulty: Hard.
+- Related Topics: Dynamic Programming, Prefix Sum.
+- Similar Questions: .
+
+## Problem
+
+You are given three integers `n`, `m` and `k`. Consider the following algorithm to find the maximum element of an array of positive integers:
+
+![](https://assets.leetcode.com/uploads/2020/04/02/e.png)
+
+You should build the array arr which has the following properties:
+
+
+	
+- `arr` has exactly `n` integers.
+	
+- `1 <= arr[i] <= m` where `(0 <= i < n)`.
+	
+- After applying the mentioned algorithm to `arr`, the value `search_cost` is equal to `k`.
+
+
+Return **the number of ways** to build the array `arr` under the mentioned conditions. As the answer may grow large, the answer **must be** computed modulo `109 + 7`.
+
+ 
+Example 1:
+
+```
+Input: n = 2, m = 3, k = 1
+Output: 6
+Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
+```
+
+Example 2:
+
+```
+Input: n = 5, m = 2, k = 3
+Output: 0
+Explanation: There are no possible arrays that satisify the mentioned conditions.
+```
+
+Example 3:
+
+```
+Input: n = 9, m = 1, k = 1
+Output: 1
+Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
+```
+
+ 
+**Constraints:**
+
+
+	
+- `1 <= n <= 50`
+	
+- `1 <= m <= 100`
+	
+- `0 <= k <= n`
+
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number} n
+ * @param {number} m
+ * @param {number} k
+ * @return {number}
+ */
+var numOfArrays = function(n, m, k) {
+    return helper(n, m, k, 0, {});
+};
+
+var helper = function (n, m, k, maxSoFar, dp) {
+    if (n === 0 && k === 0) return 1;
+    if (n === 0) return 0;
+    if (maxSoFar === m && k > 0) return 0;
+    var key = `${n}-${k}-${maxSoFar}`;
+    if (dp[key] !== undefined) {
+        return dp[key];
+    }
+    var mod = Math.pow(10, 9) + 7;
+    var ans = 0;
+    // choose num less than the current max value
+    for (var i = 1; i <= maxSoFar; i++) {
+        ans = (ans + helper(n - 1, m, k, maxSoFar, dp)) % mod;
+    }
+    // choose num bigger than the current max value
+    for (var j = maxSoFar + 1; j <= m; j++) {
+        ans = (ans + helper(n - 1, m, k - 1, j, dp)) % mod;
+    }
+    dp[key] = ans;
+    return dp[key];
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n * m ^ 2 * k).
+* Space complexity : O(n * m * k).
