题目描述

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

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

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

样例

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

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

限制

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

算法

(动态规划) $O(nk)$

1. 此题的数据范围考虑用动态规划来解决，为了方便，需要从小到大按顺序安放数字。
2. 状态 $f(i,j)$ 表示使用了 1 ~ i 这 $i$ 个数字，产生了 $j$ 个逆序对的方案数。
3. 初始值 $f(1, 0) = 1$，其余为 0。
4. 转移时，对于 $f(i, j)$ 考虑 i 这个数字放的位置。由于当前 i 这个数字是当前安放的所有数字中最大的，所以安放 i 这个数字可能产生 0 到 i - 1 个逆序对。故转移很容易就能写出，即如果 $j < i$，则 $f(i, j) = f(i - 1, 0) + f(i - 1, 1) + … + f(i - 1, j)$；否则 $f(i, j) = f(i - 1, j - i + 1) + f(i - 1, j - i + 2) + … + f(i - 1, j)$。
5. 单纯按照以上方程转移，会导致 $O(n^2 k)$的复杂度。考虑定义前缀和数组 $s(i, j) = f(i, 0) + f(i, 1) + f(i, 2) + … + f(i, j)$。则转移按照两种情况，可以优化为 $f(i, j) = s(i - 1, j)$ 和 $f(i, j) = s(i - 1, j) - s(i - 1, j - i)$。

时间复杂度

• 状态数为 $O(nk)$，转移数优化后为 $O(1)$，故总时间复杂度为 $O(nk)$。

C++ 代码

class Solution {
public:
    int kInversePairs(int n, int k) {
        int mod = 1000000007;
        vector<vector<int>> f(n + 1, vector<int>(k + 1)), s(n + 1, vector<int>(k + 1));
        f[1][0] = 1;
        for (int j = 0; j <= k; j++)
            s[1][j] = 1;

        for (int i = 2; i <= n; i++)
            for (int j = 0; j <= k; j++) {
                if (j < i)
                    f[i][j] = s[i - 1][j];
                else
                    f[i][j] = (s[i - 1][j] - s[i - 1][j - i] + mod) % mod;

                if (j == 0)
                    s[i][j] = f[i][j];
                else
                    s[i][j] = (s[i][j - 1] + f[i][j]) % mod;
            }
        return f[n][k];
    }
};