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