统计逆序对数目

2024-10-17

leetcode

题目：

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：

i < j 且 nums[i] > nums[j]

请你返回 [0, 1, 2, ..., n - 1] 的排列perm 的数目，满足对所有的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。由于答案可能会很大，将它对 109 + 7 取余后返回。

示例 1：

输入：n = 3, requirements = [[2,2],[0,0]]

输出：2

解释：

两个排列为：[2, 0, 1]

前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2] 的逆序对数目为 0 个。

[1, 2, 0]

前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。
前缀 [1] 的逆序对数目为 0 个。

示例 2：

输入：n = 3, requirements = [[2,2],[1,1],[0,0]]

输出：1

解释：

唯一满足要求的排列是 [2, 0, 1] ：

前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2, 0] 的逆序对为 (0, 1) 。
前缀 [2] 的逆序对数目为 0 。

示例 3：

输入：n = 2, requirements = [[0,0],[1,0]]

输出：1

解释：

唯一满足要求的排列为 [0, 1] ：

前缀 [0] 的逆序对数目为 0 。
前缀 [0, 1] 的逆序对为 (0, 1) 。

提示：

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [endi, cnti]
0 <= endi <= n - 1
0 <= cnti <= 400
输入保证至少有一个 i 满足 endi == n - 1 。
输入保证所有的 endi 互不相同。

思路：

一、寻找子问题看示例 1，要求构造逆序对为 2 的排列。讨论最后一个数填什么：

填 2，那么前面不会有比 2 大的数，这意味着剩下的 n−1=2 个数的逆序对等于 2−0=2。
填 1，那么前面一定有 1 个比 1 大的数，这意味着剩下的 n−1=2 个数的逆序对等于 2−1=1。
填 0，那么前面一定有 2 个比 0 大的数，这意味着剩下的 n−1=2 个数的逆序对等于 2−2=0。

这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

二、状态定义与状态转移方程因为要解决的问题都形如「前 i 个数的逆序对为 j 时的排列个数」，所以用它作为本题的状态定义 dfs(i,j)。

直接考虑第 i 个数 perm[i] 和前面 perm[0] 到 perm[i−1] 可以组成的逆序对的个数：

前面有 k 个数比 perm[i] 大，组成了 k 个逆序对，那么问题变成前 i−1 个数的逆序对为 j−k 时的排列个数，即 dfs(i−1,j−k)。

累加得 \(dfs(i,j)= k=0 ∑ min(i,j) dfs(i−1,j−k)\) 其中 min(i,j) 是因为前面只有 i 个数，至多和 perm[i] 组成 i 个逆序对。

⚠注意：我们不需要知道每个位置具体填了什么数。无论之前填了什么数，只要 perm[i] 填的是剩余元素的最大值，那么 k 就是 0；只要 perm[i] 填的是剩余元素的次大值，那么 k 就是 1；依此类推。

除此以外，设 req[i] 是前 i 个数的逆序对个数（没有要求就是 −1），如果 req[i−1]≥0，则无需枚举 k，分类讨论：

如果 j<req[i−1] 或者 j−i>req[i−1]，则无法满足，dfs(i,j)=0。
否则 dfs(i,j)=dfs(i−1,req[i−1])。

递归边界：dfs(0,0)=1，此时找到了一个符合要求的排列。

递归入口：dfs(n−1,req[n−1])，也就是答案。

根据题意，req[0] 一定为 0。代码实现时，可以在递归之前判断 req[0]>0 的情况，如果满足则直接返回 0。

三、递归搜索 + 保存递归返回值 = 记忆化搜索考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。

注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i,j) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1。

代码：

class Solution {
    const int MOD = 1'000'000'007;
public:
    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
        vector<int> req(n, -1);
        req[0] = 0;
        for (auto& p : requirements) {
            req[p[0]] = p[1];
        }
        if (req[0]) {
            return 0;
        }

        int m = ranges::max(req);
        vector<vector<int>> memo(n, vector<int>(m + 1, -1)); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int i, int j) -> int {
            if (i == 0) {
                return 1;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = 0;
            if (int r = req[i - 1]; r >= 0) {
                if (j >= r && j - i <= r) {
                    res = dfs(dfs, i - 1, r);
                }
            } else {
                for (int k = 0; k <= min(i, j); k++) {
                    res = (res + dfs(dfs, i - 1, j - k)) % MOD;
                }
            }
            return res;
        };
        return dfs(dfs, n - 1, req[n - 1]);
    }
};