---

0629. K 个逆序对数组

• 标签：动态规划
• 难度：困难

题目链接

• 0629. K 个逆序对数组 - 力扣

题目大意

描述：

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

给定两个整数 $n$ 和 $k$。

要求：

找出所有包含从 $1$ 到 $n$ 的数字，且恰好拥有 $k$ 个「逆序对」的不同的数组的个数。由于答案可能很大，只需要返回对 $10^9 + 7$ 取余的结果。

说明：

• $1 \le n \le 10^{3}$。
• $0 \le k \le 10^{3}$。

示例：

• 示例 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：动态规划

这道题目要求计算恰好有 $k$ 个逆序对的排列数量。使用动态规划求解。

定义 $dp[i][j]$ 表示使用数字 $1$ 到 $i$ 组成的排列中，恰好有 $j$ 个逆序对的排列数量。

状态转移：

• 当我们在前 $i - 1$ 个数字的排列中插入数字 $i$ 时，可以插入到任意位置。
• 如果插入到最后，不产生新的逆序对。
• 如果插入到倒数第二个位置，产生 1 个新的逆序对。
• 如果插入到第一个位置，产生 $i - 1$ 个新的逆序对。
• 因此：$dp[i][j] = \sum_{t=0}^{\min(j, i-1)} dp[i-1][j-t]$

优化：使用前缀和优化，避免重复计算。

思路 1：代码

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        
        # dp[i][j] 表示使用 1 到 i 的数字，恰好有 j 个逆序对的排列数
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        # 初始化：1 个数字，0 个逆序对
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            dp[i][0] = 1  # 0 个逆序对只有一种排列（升序）
            
            for j in range(1, k + 1):
                # dp[i][j] = sum(dp[i-1][j-t]) for t in range(min(j, i-1) + 1)
                # 使用前缀和优化
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD
                
                # 减去超出范围的部分
                if j >= i:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]) % MOD
        
        return dp[n][k]

思路 1：复杂度分析

• 时间复杂度：$O(n \times k)$，需要填充 $n \times k$ 的动态规划表。
• 空间复杂度：$O(n \times k)$，需要使用二维数组存储动态规划状态。可以优化到 $O(k)$。