题目描述
给你三个整数 n、m 和 k
。下图描述的算法用于找出正整数数组中最大的元素。
请你生成一个具有下述属性的数组 arr
:
arr
中有 n
个整数。
1 <= arr[i] <= m
其中 (0 <= i < n)
。
将上面提到的算法应用于 arr
,search_cost
的值等于 k 。返回上述条件下生成数组 arr
的 方法数,对 10^9 + 7 取余
算法
设 $dp[n][i][k]$为长度为 n,最大值为 i,search_cost 为 k 的数组的数目,则 $\sum_{i=1}^{m}dp[n][i][k]∑ _{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]\sum_{ j=1}^{ i−1} dp[n−1][j][k−1] $种,即前 n-1 个元素都小于 i;
而当最大值出现在前 n-1n−1 个元素之中时,数组末尾的元素可以从 11 到 ii 中任意选取,即有 $i \times dp[n-1][i][k]$ 种构造方法.
状态转移方程:
$dp[n][i][k]=i×dp[n−1][i][k]+i×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