How can dynamic programming help solve 'Count the Number of Inversions'?

Dynamic programming helps by storing intermediate results for permutation lengths and inversion counts, avoiding recomputation and improving efficiency.

What is the best data structure to track inversions in this problem?

A Fenwick Tree or Binary Indexed Tree (BIT) is optimal for tracking inversions because it allows for efficient updates and prefix sum queries.

How do multiple inversion constraints affect the dynamic programming solution?

Multiple constraints must be integrated into the DP solution by ensuring that the inversion counts match the specified requirements for each prefix.

What is the time complexity of solving this problem?

The time complexity can be `O(n^2 * m)`, where `n` is the array length and `m` is the maximum inversion count. Optimizations may reduce this complexity.

What are the common pitfalls in solving 'Count the Number of Inversions'?

Common pitfalls include inefficient inversion counting, failure to correctly update the DP table, and missing constraints for specific prefixes.

#3193

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计逆序对的数目

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [end i , cnt i ] 表示这个要求中的末尾下标和逆序对的数目。整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个逆序对： i 且 nums[…

数组动态规划

题目描述

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

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

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

请你返回 [0, 1, 2, ..., n - 1] 的排列 perm 的数目，满足对所有的 requirements[i] 都满足 perm[0..end_i] 中恰好有 cnt_i 个逆序对。

由于答案可能会很大，将它对 10⁹ + 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] 没有逆序对。

提示：

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示 $[0..i]$ 的排列中，逆序对数量为 $j$ 的排列数。考虑下标为 $i$ 的数 $a_i$ 与前面 $i$ 个数的大小关系。如果 $a_i$ 比前面 $k$ 个数小，那么前面的 $k$ 个数与 $a_i$ 都构成了逆序对，逆序对数量为 $k$ 。因此，我们可以得到状态转移方程：

f[i][j] = \sum_{k=0}^{\min(i, j)} f[i-1][j-k]

由于题目要求 $[0..\textit{end}_i]$ 的逆序对数量为 $\textit{cnt}_i$ ，因此，当我们计算 $i = \textit{end}_i$ 时，我们只需要计算 $f[i][\textit{cnt}_i]$ 即可。其余的 $f[i][..]$ 都为 $0$ 。

时间复杂度 $O(n \times m \times \min(n, m))$ ，空间复杂度 $O(n \times m)$ 。其中 $m$ 是逆序对数量的最大值。本题中 $m \le 400$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        req = [-1] * n
        for end, cnt in requirements:
            req[end] = cnt
        if req[0] > 0:
            return 0
        req[0] = 0
        mod = 10**9 + 7
        m = max(req)
        f = [[0] * (m + 1) for _ in range(n)]
        f[0][0] = 1
        for i in range(1, n):
            l, r = 0, m
            if req[i] >= 0:
                l = r = req[i]
            for j in range(l, r + 1):
                for k in range(min(i, j) + 1):
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
        return f[n - 1][req[n - 1]]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands the concept of dynamic programming for state transitions.
question_mark
Candidate can efficiently calculate and update inversion counts using data structures like Fenwick Tree.
question_mark
Candidate identifies the challenge of handling multiple requirements and can incorporate them into the DP approach.

warning

常见陷阱

外企场景

error
Not accounting for all inversion constraints, which can lead to incorrect permutation counts.
error
Inefficient inversion counting leading to excessive time complexity.
error
Failure to properly update the DP table when new elements are added, causing incorrect counts of valid permutations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle permutations with additional constraints on element values.
arrow_right_alt
Add a requirement to count the number of inversions for subsets of the array, not just prefixes.
arrow_right_alt
Allow the inversion count to be variable for each prefix, testing how the algorithm handles different ranges of inversion constraints.

help

常见问题

外企场景

继续练习

#3192 使二进制数组全部等于 1 的最少操作次数 II #3196 最大化子数组的总成本 #3186 施咒的最大总伤害