在C ++中可以找到最大精确K比较的构建数组
假设我们有三个整数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（（amodm）+（bmodm））modm
定义大小为54x54x105的数组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，则-
除此以外
returndp[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