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] mod m

• 如果j> = i，则-

• dp [i，j]：=（dp [i，j]-dp [i – 1，j-i] + m）mod m

• 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