Hard

题目描述

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

给定两个整数 n 和 k，返回由数字 1 到 n 组成的不同数组的数量，使得这些数组恰好有 k 个逆序对。由于答案可能很大，请返回对 10^9 + 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

解题思路

这是一个动态规划问题，关键是理解如何构建状态转移关系。

核心思路：

定义 dp[i][j] 表示使用数字 1 到 i 构成的数组中恰好有 j 个逆序对的方案数。

状态转移分析：

当我们从长度为 i-1 的数组扩展到长度为 i 的数组时，需要在某个位置插入数字 i。假设我们将数字 i 插入到倒数第 p+1 个位置（从右往左数），那么数字 i 会与它右边的 p 个数字形成逆序对。

因此状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-min(i-1, j)]

其中 min(i-1, j) 是因为最多只能产生 i-1 个新的逆序对。

优化方法：

直接计算上述求和会导致 O(n²k) 的时间复杂度。我们可以利用前缀和优化，将时间复杂度降低到 O(nk)。

设 sum[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]，则：

dp[i][j] = sum[i-1][j] - sum[i-1][j-min(i, j+1)]

代码实现

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        
        // 初始化：长度为1的数组只有0个逆序对
        dp[1][0] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i][0] = 1; // 有序数组总是0个逆序对
            
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i][j-1]; // 前缀和
                
                if (j >= i) {
                    dp[i][j] = (dp[i][j] - dp[i-1][j-i] + MOD) % MOD;
                }
                
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        # 初始化：长度为1的数组只有0个逆序对
        dp[1][0] = 1
        
        for i in range(2, n + 1):
            dp[i][0] = 1  # 有序数组总是0个逆序对
            
            for j in range(1, k + 1):
                dp[i][j] = dp[i][j-1]  # 前缀和
                
                if j >= i:
                    dp[i][j] = (dp[i][j] - dp[i-1][j-i]) % MOD
                
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
        
        return dp[n][k]

public class Solution {
    public int KInversePairs(int n, int k) {
        const int MOD = 1000000007;
        int[,] dp = new int[n + 1, k + 1];
        
        // 初始化：长度为1的数组只有0个逆序对
        dp[1, 0] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i, 0] = 1; // 有序数组总是0个逆序对
            
            for (int j = 1; j <= k; j++) {
                dp[i, j] = dp[i, j - 1]; // 前缀和
                
                if (j >= i) {
                    dp[i, j] = (dp[i, j] - dp[i - 1, j - i] + MOD) % MOD;
                }
                
                dp[i, j] = (dp[i, j] + dp[i - 1, j]) % MOD;
            }
        }
        
        return dp[n, k];
    }
}

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function(n, k) {
    const MOD = 1e9 + 7;
    const dp = Array(n + 1).fill(null).map(() => Array(k + 1).fill(0));

    // 初始化：长度为1的数组只有0个逆序对
    dp[1][0] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i][0] = 1; // 有序数组总是0个逆序对

        for (let j = 1; j <= k; j++) {
            dp[i][j] = dp[i][j - 1]; // 前缀和

            if (j >= i) {
                dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD;
            }

            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
        }
    }

    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(nk)需要填充 n×k 的动态规划表，每个状态的转移是 O(1)
空间复杂度O(nk)需要 n×k 的二维数组存储状态

相关题目