C ++中的K个逆对数组
假设我们有两个整数n和k，我们必须找到多少个不同的数组，这些数组由1到n的数字组成，因此恰好有k个逆对。逆对适用于数组中的第ith个元素和第j个元素，如果i<j和a[i]>a[j]，则称为逆对。这里的答案可能非常大，答案应为模$10^{9}$+7。
因此，如果输入像n=3且k=1，则输出将为2，因为数组[1,3,2]和[2,1,3]将只有一对逆对。
为了解决这个问题，我们将遵循以下步骤-
定义一个大小为（n+1）x（k+1）的2D数组dp
dp[0，0]：=1
对于初始化i：=1，当i<=n时，更新（将i增加1），-
dp[i，j]：=dp[i，j-1]+dp[i–1，j]
dp[i，j]：=dp[i，j]modm
如果j>=i，则-
dp[i，j]：=（dp[i，j]-dp[i–1，j-i]+m）modm
dp[i，0]：=1
对于初始化j：=1，当j<=k时，更新（将j增加1），-
返回dp[n，k]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int kInversePairs(int n, int k) {
vector < vector <int> > dp(n + 1, vector <int>(k + 1));
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
dp[i][0] = 1;
for(int j = 1; j <= k; j++){
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
dp[i][j] %= m;
if(j >= i){
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m;
}
}
}
return dp[n][k];
}
};
main(){
Solution ob;
cout << (ob.kInversePairs(4,2));
}输入值
4 2
输出结果
5