问题描述 链接到标题

629. K个逆序对数组 (Hard)

给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第 i 个和第 j 个元素，如果满 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 10 + 7 的值。

示例 1:

输入: n = 3, k = 0
输出: 1
解释:
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2:

输入: n = 3, k = 1
输出: 2
解释:
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

说明:

  1. n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

解题思路 链接到标题

像这种答案需要取模的题，解题思路一般都是动态规划；

以dp[n][k]表示考虑前$n$个数时，逆序对刚好为$k$个的方案数，为了找到递推关系，我们需要考虑数$n$的位置，假设数$n$位于第$n$个位置，那么dp[n][k] = dp[n - 1][k]（因为没有数能与$n$组成逆序对，相当于不用考虑数$n$），假设数$n$位于第$n - 1$个位置，那么dp[n][k] = dp[n - 1][k - 1]，所以，我们可以求得递推关系：

  • 当k >= n - 1时，$dp[n][k] = \sum\limits_{i=0}^{n-1}dp[n-1][k-i]$
  • 当k < n - 1时，$dp[n][k] = \sum\limits_{i=0}^{k}dp[n][i]$

但是直接用这个递推关系式，时间复杂度为$O(nk^2)$，可能会超时，我们考虑用$dp[n][k] - dp[n][k - 1]$，可以发现新的递推关系式：

  • 如果k <= n - 1，$dp[n][k] = dp[n][k - 1] + dp[n - 1][k]$
  • 如果k > n - 1，$dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n]$

代码 链接到标题 

class Solution {
  public:
    int kInversePairs(int n, int k) {
        vector<vector<long>> dp(n + 1, vector<long>(k + 1, 0));
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = 1;
        }
        int mod = 1000000007;
        if (k > n * (n - 1) / 2) {
            return 0;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k && j <= (i * (i - 1) / 2); ++j) {
                if (j <= i - 1) {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - i] + mod) % mod;
                }
            }
        }
        return dp[n][k];
    }
};