假设我们有三个整数n，m和k。如果我们有以下算法来找到正整数数组的最大元素-
max_val := -1 max_ind := -1 search_cost := 0 n := size of arr for initialize i := 0, when i < n, update (increase i by 1), do: if max_val < arr[i], then: max_val := arr[i] max_ind := i (increase search_cost by 1) return max_ind
我们必须使数组arr具有以下条件：arr具有正好n个整数。所有元素arr [i]的范围都在1到m（包括）之间（0 <= i <n）。将上述算法应用于arr后，值search_cost等于k。我们必须找到在上述条件下构建数组arr的多种方法。答案可能非常大，因此将以10 ^ 9 + 7取模。
因此，如果输入像n = 2，m = 3，k = 1，则输出将是6，因为可能的数组是[1、1]，[2、1]，[2、2]，[3 ，1]，[3、2] [3、3]
为了解决这个问题，我们将遵循以下步骤-
m：= 10 ^ 9 + 7
定义一个函数add()，这将需要a，b，
return（（a mod m）+（b mod m））mod m
定义大小为54 x 54 x 105的数组dp。
定义一个函数help()，它将使用idx，m，k，currVal，n，
如果k <0，则-
返回0
如果idx与n + 1相同，则-
当k为0时返回true
如果dp [idx，k，currVal + 1]不等于-1，则-
返回dp [idx，k，currVal + 1]
ret：= 0
对于初始化i：= 1，当i <= m时，更新（将i增加1），-
ret：=添加（帮助（idx + 1，m，k，max(currVal,i)，n），ret）
ret：=添加（帮助（idx + 1，m，k-1，max(currVal,i)，n），ret）
如果i> currVal，则-
除此以外
return dp [idx，k，currVal + 1] = ret
从主要方法中执行以下操作-
对于初始化i：= 0，当i <54时，更新（将i增加1），请执行-
对于初始化k：= 0，当k <105时，更新（将k增加1），-
dp [i，j，k]：= -1
对于初始化j：= 0，当j <54时更新（将j增加1），执行-
ret：= help(1,m,k,-1,n)
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b) {
return ((a % m) + (b % m)) % m;
}
int dp[54][54][105];
int help(int idx, int m, int k, int currVal, int n) {
if (k < 0)
return 0;
if (idx == n + 1) {
return k == 0;
}
if (dp[idx][k][currVal + 1] != -1)
return dp[idx][k][currVal + 1];
int ret = 0;
for (int i = 1; i <= m; i++) {
if (i > currVal) {
ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret);
}
else {
ret = add(help(idx + 1, m, k, max(currVal, i), n), ret);
}
}
return dp[idx][k][currVal + 1] = ret;
}
int numOfArrays(int n, int m, int k) {
for (int i = 0; i < 54; i++)
for (int j = 0; j < 54; j++)
for (int k = 0; k < 105; k++)
dp[i][j][k] = -1;
int ret = help(1, m, k, -1, n);
return ret;
}
};
main() {
Solution ob;
cout << (ob.numOfArrays(2, 3, 1));
}2, 3, 1
输出结果
6