What is the K Inverse Pairs Array problem?

The K Inverse Pairs Array problem asks for the number of arrays of size n, formed by numbers from 1 to n, that contain exactly k inverse pairs.

How do you approach solving K Inverse Pairs Array?

The problem is solved using dynamic programming. A table is created to track the number of ways to form arrays with exact inverse pairs, and transitions are made based on adding elements.

What is the time complexity of solving K Inverse Pairs Array?

The time complexity is O(n * k) where n is the size of the array and k is the number of inverse pairs.

Why do we use modulo 10^9 + 7 in this problem?

We use modulo 10^9 + 7 to prevent overflow and ensure the results fit within manageable limits.

Can this problem be solved without dynamic programming?

While dynamic programming is the most efficient approach, alternative methods such as divide-and-conquer or brute force could be used but are not optimal.

#629

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

K 个逆序对数组

对于一个整数数组 nums ，逆序对是一对满足 0 且 nums[i] > nums[j] 的整数对 [i, j] 。给你两个整数 n 和 k ，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。由于答案可能很大，只需要返回对 10 9 + 7 取余的结果。 …

动态规划

题目描述

对于一个整数数组 nums，逆序对是一对满足 0 <= i < j < nums.length 且 nums[i] > nums[j]的整数对 [i, j] 。

给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 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 <= 1000
0 <= k <= 1000

lightbulb

解题思路

方法一：动态规划 + 前缀和

我们定义 $f[i][j]$ 表示数组长度为 $i$ ，逆序对数为 $j$ 的数组个数。初始时 $f[0][0] = 1$ ，其余 $f[i][j] = 0$ 。

接下来我们考虑如何得到 $f[i][j]$ 。

假设前 $i-1$ 个数已经确定，现在要插入数字 $i$ ，我们讨论 $i$ 插入到每个位置的情况：

如果 $i$ 插入到第 $1$ 个位置，那么逆序对增加了 $i-1$ 个，所以 $f[i][j]+=f[i-1][j-(i-1)]$ 。
如果 $i$ 插入到第 $2$ 个位置，那么逆序对增加了 $i-2$ 个，所以 $f[i][j]+=f[i-1][j-(i-2)]$ 。
...
如果 $i$ 插入到第 $i-1$ 个位置，那么逆序对增加了 $1$ 个，所以 $f[i][j]+=f[i-1][j-1]$ 。
如果 $i$ 插入到第 $i$ 个位置，那么逆序对不变，所以 $f[i][j]+=f[i-1][j]$ 。

所以 $f[i][j]=\sum_{k=1}^{i}f[i-1][j-(i-k)]$ 。

我们注意到 $f[i][j]$ 的计算实际上涉及到前缀和，因此，我们可以使用前缀和优化计算过程。并且，由于 $f[i][j]$ 只与 $f[i-1][j]$ 有关，因此我们可以用一个一维数组来优化空间复杂度。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(k)$ 。其中 $n$ 和 $k$ 分别为数组长度和逆序对数。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * k
        s = [0] * (k + 2)
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                f[j] = (s[j + 1] - s[max(0, j - (i - 1))]) % mod
            for j in range(1, k + 2):
                s[j] = (s[j - 1] + f[j - 1]) % mod
        return f[k]

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate can clearly explain dynamic programming table construction.
question_mark
Ask the candidate to discuss the role of modulo arithmetic in maintaining large results.
question_mark
Test the candidate's understanding of how state transitions occur with array element additions.

warning

常见陷阱

外企场景

error
Failing to handle state transitions properly, which leads to incorrect calculations of inverse pairs.
error
Incorrectly applying the modulo operation, causing overflow or incorrect results.
error
Not understanding the time and space complexity trade-offs of the dynamic programming solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Optimizing space complexity by reducing the size of the DP table.
arrow_right_alt
Using a more advanced approach to optimize the time complexity further.
arrow_right_alt
Solving the problem with a non-DP approach, such as a divide-and-conquer algorithm.

help

常见问题

外企场景

继续练习

#638 大礼包 #639 解码方法 II #646 最长数对链