难度: Hard
给定三个整数 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 <= 501 <= m <= 1000 <= k <= n运行时间: 75 ms
内存: 16.5 MB
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
if n<k or m<k:
return 0
Mod=10**9+7
# f=[[[0]*(m+1) for _ in range(k+1)] for _ in range(n)]
f0=[[0]*(m+1) for _ in range(k+1)]
f1=[[0]*(m+1) for _ in range(k+1)]
for i in range(1,m+1):
f0[1][i]=1
for i in range(1,n):
for s in range(1,min(i+1,k)+1):
presum_j=0
for j in range(1,m+1):
f1[s][j]=(f0[s][j]*j + presum_j)%Mod
presum_j+=f0[s-1][j]
# f[i][s][j]=(f[i-1][s][j]*j+presum_j)%Mod
# presum_j=(presum_j+f[i-1][s-1][j])%Mod
f0,f1=f1,f0
return sum(f0[-1])%Mod
这道题目使用动态规划的方法来解决。定义动态规划数组 f[i][s][j] 表示考虑前 i 个元素，最大值为 j，且 search_cost 为 s 的数组数量。状态转移方程为：f[i][s][j] = f[i-1][s][j] * j + sum(f[i-1][s-1][1...j-1])。其中，f[i-1][s][j] * j 表示第 i 个元素可以选择 1 到 j 中的任何一个数字，而 sum(f[i-1][s-1][1...j-1]) 表示第 i 个元素选择的数字比之前的最大值 j 要大，因此 search_cost 增加了 1。为了优化空间复杂度，可以使用滚动数组的技巧，交替使用 f0 和 f1 两个数组来存储动态规划的状态。
时间复杂度: O(n * k * m)
空间复杂度: O(k * m)
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
if n<k or m<k:
return 0
Mod=10**9+7
f0=[[0]*(m+1) for _ in range(k+1)]
f1=[[0]*(m+1) for _ in range(k+1)]
for i in range(1,m+1):
f0[1][i]=1
for i in range(1,n):
for s in range(1,min(i+1,k)+1):
presum_j=0
for j in range(1,m+1):
f1[s][j]=(f0[s][j]*j + presum_j)%Mod
presum_j+=f0[s-1][j]
f0,f1=f1,f0
return sum(f0[-1])%Mod
在这个动态规划的设置中，f[i][s][j] 表示考虑前 i 个元素，且这些元素中的最大值是 j，同时 search_cost 等于 s 的不同数组的数量。这里，i 表示数组的长度，s 表示搜索成本，j 表示数组中的最大值。
状态转移方程中的 f[i-1][s][j] * j 部分表示当第 i 个元素取值在 1 到 j 之间任何一个可能的值时，都不会改变数组的最大值和搜索成本，因此有 j 种可能。sum(f[i-1][s-1][1...j-1]) 部分表示当第 i 个元素选择的值比之前所有元素的最大值都要大时（即这个值是 j），它会使得数组的最大值增加，并且因为这个新的最大值，搜索成本也相应增加了一，所以需要加上所有可能的前 i-1 个元素构成的子数组的数量，其中数组最大值小于 j。
当 n < k 或 m < k 时，函数返回 0 是因为在题目的设置中，数组需要有 k 个不同的最大值来满足 search_cost 为 k。如果 n（数组长度）小于 k，那么不可能在数组中放置足够数量的元素来实现 k 个不同的最大值。同样，如果 m（可选的最大值）小于 k，那么也没有足够多的不同值可以用来实现 k 个不同的最大值。
在计算中使用模 10^9 + 7 主要是为了防止计算过程中的整数溢出，同时也是为了保持结果的规模可管理。10^9 + 7 是一个大的质数，常用在算法竞赛和编程题目中，因为它可以提供良好的数学性质并且适合在多数编程环境中进行高效的模算运算。