1420：生成数组（2175 分）

力扣第 185 场周赛第 4 题

题目

给定三个整数 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]

提示：

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

分析

• 遍历时更新更大的数时才会增加 k
• 因此考虑最后一个数取 m
  • 假如 k 增加了，转为求 (n-1,m-1,k-1) 的递归子问题
  • 假如 k 未增加，转为求 n-1 个数，最大值为 m（注意必须取到），成本 k 的子问题
• 为了递归，令 f(n,m,k) 代表所求的数量，g(n,m,k) 代表上述第二种情况的数量，则有
  • f(n,m,k)=g(n,m,k)+f(n,m-1,k)
  • g(n,m,k)=f(n-1,m-1,k-1)+g(n-1,m,k)*m

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

mod = 10**9+7
f = [[[0]*51 for _ in range(101)] for _ in range(51)]
g = [[[0]*51 for _ in range(101)] for _ in range(51)]
for j in range(101):
    f[0][j][0] = 1
for i in range(1,51):
    for j in range(1,101):
        for k in range(1,51):
            g[i][j][k] = (f[i-1][j-1][k-1]+g[i-1][j][k]*j)%mod
            f[i][j][k] = (f[i][j-1][k]+g[i][j][k])%mod

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        return f[n][m][k]

0 ms