原文链接: https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons

英文原文

Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

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 10^9 + 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]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

 

Constraints:

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

中文题目

给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。

请你生成一个具有下述属性的数组 arr ：

• arr 中有 n 个整数。
• 1 <= arr[i] <= m 其中 (0 <= i < n) 。
• 将上面提到的算法应用于 arr ，search_cost 的值等于 k 。

返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

 

示例 1：

输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

示例 2：

输入：n = 5, m = 2, k = 3
输出：0
解释：没有数组可以满足上述条件

示例 3：

输入：n = 9, m = 1, k = 1
输出：1
解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]

示例 4：

输入：n = 50, m = 100, k = 25
输出：34549172
解释：不要忘了对 1000000007 取余

示例 5：

输入：n = 37, m = 17, k = 7
输出：418930126

 

提示：

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

通过代码

高赞题解

设 $dp[n][i][k]$ 为长度为 $n$，最大值为 $i$，search_cost 为 $k$ 的数组的数目，则 $\sum_{i=1}^{m}dp[n][i][k]$ 即为所求．

边界条件 $dp[0][i][k] = dp[n][0][k] = dp[n][i][0] = 0$，$dp[1][i][1] = 1$，对于其它的 $n, i, k$，分两种情况考虑：

当最大值 $i$ 恰好只出现在数组末尾时，构造的方法有 $\sum_{j=1}^{i-1}dp[n-1][j][k-1]$ 种，即前 $n-1$ 个元素都小于 $i$；

而当最大值出现在前 $n-1$ 个元素之中时，数组末尾的元素可以从 $1$ 到 $i$ 中任意选取，即有 $i \times dp[n-1][i][k]$ 种构造方法．

综上所述，有

$$dp[n][i][k] = i \times dp[n-1][i][k] + \sum_{j=1}^{i-1}dp[n-1][j][k-1]$$

代码：

class Solution:
    def f(self, n, i, k):
        if (self.tmp[n][i][k] != -1):
            return self.tmp[n][i][k]
        if n == 0 or k == 0 or i == 0:
            self.tmp[n][i][k] = 0
            return 0
        if n == 1 and k == 1:
            self.tmp[n][i][k] = 1
            return 1
        r=0
        for j in range(1, i):
            r += self.f(n-1, j, k-1)
            r %= 1000000007
        r += self.f(n-1, i, k)*i
        r %= 1000000007
        self.tmp[n][i][k] = r
        return r
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        self.tmp = [[[-1 for t in range(k+1)] for j in range(m+1)] for i in range(n+1)]
        r = 0
        for i in range(1, m+1):
            r += self.f(n, i, k)
            r %= 1000000007
        return r

统计信息

通过次数	提交次数	AC比率
2518	4188	60.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言